From: Charles A. Crayne on
On 1 Oct 2005 10:52:29 -0700
"randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> wrote:

:That's way it's a relatively safe assumption to pretend that the x86
:*is* an infinite machine and assume that the theory applied to Turing
:machines applies to x86 systems.

Let me attempt, once again, to demonstrate that your assumption is far less
safe than you wish us to believe:

To begin with, I can easily design an 'x86-like' architecture such that,
for all possible programs which run on that architecture, it is trivial to
determine if the program halts.

In addition, for the existing x86 architecture, or any other reasonable
architecture, I can easily design a programming language such that, for all
possible programs which can be written in that language, it is trivial to
determine if the program halts.

Furthermore, for any HLL, I can design a compiler such that, for all
possible programs generated by that compiler, it is trivial to determine if
the program halts.

Therefore, for real world programs, one must consider not only the
architecture on which it is to be run, but all the other constraints
imposed upon such programs during the process of turning an algorithm into
a program, before claiming similarity to a Turing machine process.

-- Chuck
From: Alex McDonald on
Charles A. Crayne wrote:
> On 1 Oct 2005 10:52:29 -0700
> "randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> wrote:
>
> :That's way it's a relatively safe assumption to pretend that the x86
> :*is* an infinite machine and assume that the theory applied to Turing
> :machines applies to x86 systems.
>
> Let me attempt, once again, to demonstrate that your assumption is far less
> safe than you wish us to believe:
>
> To begin with, I can easily design an 'x86-like' architecture such that,
> for all possible programs which run on that architecture, it is trivial to
> determine if the program halts.
>

Then your machine and its programming language would have to be Turing
incomplete. To quote; "[T]here are problems solvable by Turing-complete
languages that cannot be solved by languages with finite looping
capabilities (i.e. languages that guarantee any program will halt)."

See http://en.wikipedia.org/wiki/Turing-complete and
http://en.wikipedia.org/wiki/Computability_theory for an overview
introduction.

--
Regards
Alex McDonald
From: wolfgang kern on

"T.M. Sommers" wrote:

| > .. Show me the border of the universe ...
|
| It is possible for a space to be finite yet unbounded.
| Consider the surface of a sphere, for example.

I can't see 'space' on a 'surface' without a Y-direction ;)
'flat folks' on a sphere will find a limited environment
by just travel straight and reaching the start point again.

Yes, limits are found easy, but as only our measurments are
limited by our capabilities, this does not neccessarily mean
that everything must have a limit or a border line.

__
wolfgang


From: Alex McDonald on
wolfgang kern wrote:
> "T.M. Sommers" wrote:
>
> | > .. Show me the border of the universe ...
> |
> | It is possible for a space to be finite yet unbounded.
> | Consider the surface of a sphere, for example.
>
> I can't see 'space' on a 'surface' without a Y-direction ;)

Z direction.

> 'flat folks' on a sphere will find a limited environment
> by just travel straight and reaching the start point again.

Yes. The surface of sphere is a 3 dimensional finite yet unbounded
(edgeless) 2 dimensional space. It's difficult to imagine, but a
hyper-sphere (a 4 dimensional sphere) is a finite yet unbounded 3
dimensional space for beings like us.

>
> Yes, limits are found easy, but as only our measurments are
> limited by our capabilities, this does not neccessarily mean
> that everything must have a limit or a border line.

Our measurements of what exactly?

--
Regards
Alex McDonald
From: Charles A. Crayne on
On Sun, 2 Oct 2005 09:27:02 +0000 (UTC)
Alex McDonald <alex_mcd(a)btopenworld.com> wrote:

:Then your machine and its programming language would have to be Turing
:incomplete.

Strictly speaking, all real machines are Turing-incomplete, since they do
not have infinite storage, although the specific example I have in mind is,
indeed, one which forces finite looping.

My purpose, however was not to suggest that any such machine should
actually be build, but rather to demonstrate that it is not safe to assume
Turing completeness for any given combination of machine architecture and
programming language, let alone the additional constraints imposed by
specific hardware configurations, operating systems, and compilers.

-- Chuck