🚀 go-pugleaf

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             =      /\       =