Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!vtserf!creatures!csgrad!lavinus
From: lavinus@csgrad.cs.vt.edu
Newsgroups: comp.lang.misc
Subject: Re: Turing equivalence (was first-class composable functions)
Message-ID: <926@creatures.cs.vt.edu>
Date: 13 Feb 91 15:55:54 GMT
References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <1991Feb11.164821.10486@spool.cs.wisc.edu> <320@smds.UUCP>
Sender: usenet@creatures.cs.vt.edu
Reply-To: lavinus@csgrad.cs.vt.edu ()
Organization: Virginia Tech Computer Science, Blacksburg, VA
Lines: 31

Well, I guess I'll throw my two cents' worth into this whole Turing machine
debate:

A Turing machine, by definition, has an infinite tape.  Therefore, no computer
in existence can simulate a "real" Turing machine, dynamic allocation or not.
What a real-life computer CAN simulate is a Linear Bounded Automata, i.e.,
a Turing machine with a finite tape.  However, if one consults any Formal
Languages textbook, one will find that these two machines are tremendously
different in terms of computing power.  For instance, only a Turing machine
can run an acceptor for a recursively enumerable language (Level 0 on the 
Chomsky hierarchy), while the best one can to with an LBA is to parse a
context-sensitive (level 1) grammar.  BUT... whether or not a particular
machine can implement a real-life programming language is not a function of
the size of the programs that may be written in that language, but a function
of the complexity of the grammer which describes that language.  To date,
there are no level 0 programming languages, because they're incredibly
difficult to parse.  So the point of all this is that any language for which
a compiler can be written on a real computer can be accepted by an LBA (if
you believe Church's thesis, anyway), and any language accepted by an LBA
can be accepted by a Turing machine, so, assuming that Church's thesis is
correct, every modern-day programming language is Turing-equivalent to every
other one.

Adios...

Joe Lavinus
--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
= Joseph W. Lavinus                           =     \  /      =
= Virginia Tech, Blacksburg, Virginia         =      \/__V    =
= email: lavinus@csgrad.cs.vt.edu             =      /\       =