[FOM] 2,3 Turing machine proof controversy

Vaughan Pratt pratt at cs.stanford.edu
Fri Nov 9 15:26:17 EST 2007

```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
```

More information about the FOM mailing list