[FOM] 2,3 Turing machine proof controversy

[Vaughan Pratt]

Alexander Smith wrote:
> (I haven't seen the famous proof that LBAs cannot be universal,

LBAs can't be universal because they have a decidable halting problem. 
(Whether a given Turing machine M halts on a given input of length n 
reduces to the problem of finding a suitable path in the graph G whose 
vertices are the possible configurations of M and whose edges are the 
possible transitions between those configurations.  When M is an LBA, G 
is of size exponential in n, whence if n is finite the problem is 
decidable.)

> but suspect that one of
> the assumptions or definitions it makes is that LBAs only accept a
> finite amount of input, because without that assumption it seems
> pretty easy to prove that LBAs are universal because when given an
> infinite amount of input they are equivalent to Turing machines;
> please let me know if I'm wrong about this.)

Quite right, this being case of infinite n in the above argument, making 
the linear bound vacuous and hence M an ordinary Turing machine (less 
the usual restriction to starting with only finitely many nonblank tape 
cells).

(To keep this message short I've deleted most of your text; the link
http://cs.nyu.edu/pipermail/fom/2007-November/012227.html
will help interested third parties find your post more easily.)

> Imagine the following input:
> 
> ...__R0110_01X_R0110_01XX_110XX_R0110_01XXX_110XXX_01XXX_R...
> 
> This input tells the system to emulate the cyclic tag system for one
> step, then two steps, then three steps, then so on. The input to this
> system isn't periodic, but is simple to construct in a non-universal
> way. Is this Turing machine universal?

Let's say it's at least less objectionable than a machine that has to be 
repeatedly restarted "manually" (deus ex machina).

> With the definition I used in
> the 2,3 Turing machine universality proof, yes.

No, because this machine manages its own restarts without outside 
intervention, whereas the definition in your proof allowed manual 
restarting.  The DARPA Grand Challenge race disallowed any team 
assistance during the race, which seems equally applicable here.

Does this definition
> show that an LBA is universal? No, because there is one infinite
> input here, and an LBA can't be given an infinite amount of input.

Right, but my previous remark makes this irrelevant.

I see two challenges here.  First, can you replace outside intervention 
by a single infinite initial condition that encodes at one time the 
infinitely many restarts your proof was performing manually, so that the 
subject 2,3 machine can do its own restarting?  And second, can you 
convince the appropriate audience (I hesitate to say "committee" or 
"Rules and Guidelines" since I no longer understand the meaning of those 
terms for this prize) that the notion of universality entailed by your 
infinite initial condition falls within the scope of what the prize 
envisages as "universal."  (As I've said before I'm not the judge here, 
merely an *amicus curiae*.)  The more general the notion, the weaker 
Wolfram's Principle of Computational Equivalence---in the extreme case 
that any machine is allowed to be universal, PCE becomes vacuously true 
and hence of no scientific interest at all.

In that context it is easy to imagine that some sufficiently simply 
process for initializing tape could not possibly be universal (in the 
standard sense in which the tape must be ultimately blank in both 
directions).  For example could a Turing machine with tape alphabet 
{0,1} be universal if it is forbidden to write 0?  Surely the tape would 
fill up with ones making universality impossible.  Nice puzzle.

Vaughan