Path: utzoo!mnetor!tmsoft!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!uwm.edu!psuvax1!swatsun!swatsun!gessel From: gessel@ilium.cs.swarthmore.edu (Daniel Mark Gessel) Newsgroups: comp.lang.misc Subject: Re: Turing equivalence (was first-class composable functions) Message-ID: Date: 19 Feb 91 17:18:58 GMT References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <1991Feb11.164821.10486@spool.cs.wisc.edu> <320@smds.UUCP> <926@creatures.cs.vt.edu> <11077@pasteur.Berkeley.EDU> <26788@dime.cs.umass.edu> Sender: news@cs.swarthmore.edu Organization: Swarthmore College, Swarthmore Pa. Lines: 27 In-Reply-To: yodaiken@chelm.cs.umass.edu's message of 16 Feb 91 16:35:56 GMT Nntp-Posting-Host: ilium Many programming languages (some would say all) are "Turing Equivalent". That is, anything you can do with a Turing Machine, you can express with such a programming language. Many programs do not do all that they are cabable of on a real machine because they run out of memory, i.e. hit the limitations of the machine. REAL machines today, and probably ever, cannot run all possible programs written in a Turing Equivalent Language without restricting them in some way (i.e., a failed malloc call). One reason for using a turing equivalent language that may run out of memory on a given machine, is to have a large degree of machine independence, generally considered a valuable thing, which can use whatever resources that exist when it is running. Is the halting problem solvable then? Not for a program in such a language, but for a program in that language on a given machine. However, on a given machine, the program has "finite" power, and it is not "The Halting Problem" anymore. IMHO Dan -- Daniel Mark Gessel Internet: gessel@cs.swarthmore.edu I do not speak (nor type) representing Swarthmore College.