Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!elroy.jpl.nasa.gov!usc!wuarchive!zaphod.mps.ohio-state.edu!samsung!crackers!m2c!jjmhome!smds!rh
From: rh@smds.UUCP (Richard Harter)
Newsgroups: comp.lang.misc
Subject: Re: Turing equivalence (was first-class composable functions)
Summary: Can't do it
Message-ID: <320@smds.UUCP>
Date: 12 Feb 91 08:31:56 GMT
References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <1991Feb11.164821.10486@spool.cs.wisc.edu>
Organization: SMDS Inc., Concord, MA
Lines: 67

In article <1991Feb11.164821.10486@spool.cs.wisc.edu>, quale@picard.cs.wisc.edu (Douglas E. Quale) writes:
] 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)....

] I don't think this is quite right.  The original post refers to Turing
] equivalence of languages, not the machines that execute the programs.

	The original post is based on a quote from Dan, to wit
	"most real languages are not equivalent to Turing machines".
	I would prefer to let Dan explicate what he meant by this
	statement.

] 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.)

Now it quite true that one can write a universal Turing machine emulation
program in most implementation languages.  We all know this.  However
it is an intrinsic property of computers that they are not Turing machines.
I.e. it is not just a matter of "a limitation of the size of the computer
on which the program is run"; it is a common characteristic of all 
computers in the real universe that has been, that is, or that ever
will be.  Real computers can only run a finite number of Turing programs,
a Turing machine can run an infinite number.

What does this mean?  Well, when we say that language X is a universal
Turing machine language, what we are really saying is if a machine can
be programmed in language X and if programs written in language X can
access an unboundedly large amount of memory then that machine is a
universal Turing machine.  On the face of it, this doesn't mean much
since there are no such machines.  However we can go further and show
that if language Y has the same property then any program written in
language Y can be written in language X and vice versa.  So we have
established a criterion for determining the formal equivalence of
languages.

However there are some catches (and I hazard to guess this is what
Dan had in mind).  In most implementation languages there are explicit
limitations in the language specifications that preclude their use
as programming languages for Turing machines if you assume that the
tape (i.e. memory) is addressed.  The traditional Turing machine 
description obviates that issue by having I/O commands that reference
the contents of the current position of the tape.  If the memory is
accessed via a pointer (or array index) and the pointer is contained
in words of fixed length then the language is not universal Turing
machine equivalent.  On the other hand any given language may have
an obscure work around, so it is not a trivial matter to say whether
a particular language such as C is actually universal Turing machine
equivalent.

On the other hand, if we assume that the addressless commands to
access the current memory cell are available then all issues of dynamic
storage allocation are irrelevant -- a universal Turing machine can
be written as a fixed size program with fixed memory usage.

-- 
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.