[FOM] Simple Turing machines, Universality, Encodings, etc.

[Vaughan Pratt]

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