Path: utzoo!attcan!uunet!wuarchive!uwm.edu!uwvax!picard.cs.wisc.edu!quale From: quale@picard.cs.wisc.edu (Douglas E. Quale) Newsgroups: comp.lang.misc Subject: Re: Turing equivalence (was first-class composable functions) Message-ID: <1991Feb11.164821.10486@spool.cs.wisc.edu> Date: 11 Feb 91 16:48:21 GMT References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <319@smds.UUCP> Sender: news@spool.cs.wisc.edu (The News) Organization: U of Wisconsin CS Dept Lines: 21 In article <319@smds.UUCP> rh@smds.UUCP (Richard Harter) writes: >Programs which execute on real computers are not equivalent to Turing >machine programs in general. In real computers there is only a finite >amount of memory available (including memory of all types). As a direct >consequence there are only a finite number of programs that can be >executed on a real computer (the number is, however, very large) whereas >a universal Turing machine can execute an infinite number of distinct >programs. I don't think this is quite right. The original post refers to Turing equivalence of languages, not the machines that execute the programs. Any Turing program will use only a finite amount of memory (tape) at any particular time. It is easy to write a program to do this. It is true that due to the finite size of the machines on which these programs are executed some Turing programs won't run. But this is a limitation of the size of the computer on which the program is run, not the implementation language be it C, Pascal, Lisp or whatever. (Most languages definitions don't put limits on the size of programs, and neither do most formal semantics.) -- Doug Quale