🚀 go-pugleaf

In article <RANG.91Feb10140506@nexus.cs.wisc.edu>, 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.