[FOM] Simple Turing machines, Universality, Encodings, etc.
Vaughan Pratt
pratt at cs.stanford.edu
Mon Oct 29 03:13:37 EDT 2007
Not wanting to push my luck I'll settle for one question.
How did an argument containing such an elementary fallacy get through
the filter?
Smith gives a series of what I'll call finitary systems each of which
runs the computation for a specified number of steps, each simulating
its predecessor, then gives a non-finitary system (PDF page 21, Table of
Contents page 19) that concatenates the initial conditions of
progressively longer computations and runs one of the finitary systems
on that concatenation.
The non-finitary system is evidently universal, and the program
performing the concatenation is equally evidently non-universal. Smith
infers from this that the machine checking each of the concatenated
initial conditions in turn must be universal.
The analogous argument for numbers in place of machines and "infinite"
in place of "universal" would be, if x+y is infinite and y is finite
then x must be infinite.
This line of reasoning works for numbers but not machines. For machines
it would show that a linear-bounded automaton (LBA) is universal: a
non-universal machine can easily add to the input a string giving in
unary the number of steps to emulate the given Turing machine, and a
suitable LBA can then run the computation that far without exceeding its
linear space bound.
As Chomsky showed half a century ago, linear bounded automata are not
universal Turing machines.
Had I pushed my luck my second question would have been, who has
verified this proof that has taught an automata theory course at a
suitably accredited institution?
Vaughan Pratt
More information about the FOM
mailing list