From: Charles A. Crayne on 1 Oct 2005 20:53 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 2 Oct 2005 05:27 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 2 Oct 2005 13:03 "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 2 Oct 2005 16:16 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 2 Oct 2005 20:34
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 |