Path: utzoo!attcan!uunet!samsung!crackers!m2c!jjmhome!smds!rh From: rh@smds.UUCP (Richard Harter) Newsgroups: comp.lang.misc Subject: Re: On whether C has first-class composable functions Summary: Dan is right (!) Message-ID: <319@smds.UUCP> Date: 11 Feb 91 09:55:01 GMT References: <1991Feb7.150537.9257@spool.cs.wisc.edu> Organization: SMDS Inc., Concord, MA Lines: 42 In article , rang@cs.wisc.edu (Anton Rang) writes: > In article <6828:Feb906:14:3491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >First of all, most real languages are not equivalent to Turing machines. > Why not? > I claim that, given any Turing machine, I can write a Pascal or C > program which will perform exactly the computation that machine would > perform on a given input. (You can't do it in FORTRAN, because you > don't have dynamic memory allocation.) > Similarly, I claim that given any Pascal or C program, I can write a > description of it suitable for running on a universal Turing machine. Sorry, Dan is right on this one, and it is actually important to understand that he is right and why he is right. Turing machines do not exist in the real world -- they require as part of the definition infinite memory. The statement "real languages are not equivalent to Turing machines" isn't exact (it mixes languages and machines which are two different concepts) but the intent is clear. Real computers are finite state machine with absurdly large numbers of states. 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. The distinction is important. There are many statements that are true for Turing machines that are not true for real computers. Etc. Incidentally there are some problems with your assumption that since C and Pascal have dynamic storage allocation and Fortran does not you can do Turing machine emulation in C and Pascal and not in Fortran. I will leave them as an exercise for the reader. -- Richard Harter, Software Maintenance and Development Systems, Inc. Net address: jjmhome!smds!rh Phone: 508-369-7398 US Mail: SMDS Inc., PO Box 555, Concord MA 01742 This sentence no verb. This sentence short. This signature done.