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

[Vaughan Pratt]

Todd Rowland wrote:
> Alex Smith did not only show that the encoding of the initial condition is 
> non-universal.  He showed that the encoding is very computationally weak and 
> then concludes that the Turing machine is universal in a generalized sense.

If the encoding tells the emulator how long to run on each pass it is 
not weak enough to prevent "proving" that some resource-bounded 
automaton is universal.  Where does Smith argue that his encoding is 
sufficiently weak?

>>> 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 is an inappropriate analogy because it does work for numbers.

Good, we appear to be in agreement on that point.

> More 
> to the point is that there are no interacting systems here, just a simple 
> function that computes the initial configuration, then the Turing machine 
> runs on its own.

If the initial condition for each finite run is simply enough extra tape 
in which to perform that run, then according to your criterion there is 
"no interaction."  But this is all it takes to show that an LBA is 
universal.

> Smith's use of non-repetitive infinite initial conditions is 
> controversial, but is a natural extension of current definitions which 
> allow infinite repetitive initial conditions.

The Labrea tarpits were natural, but this wasn't much consolation to the 
fauna they trapped.

> Whenever a generalization of the definition of a universal Turing machine 
> is put forward, then the status of some machines will necessarily change 
> from 'non-universal' to 'universal'.  It is a challenge to explicitly 
> construct a machine with initial conditions similar in spirit to Smith's, 
> that is obviously too simple to be considered universal, and which is 
> performing a universal computation with those infinite initial conditions.

I hear you.

Vaughan Pratt