[FOM] 2,3 Turing machine proof controversy

[Alexander Smith]

Vaughan Pratt wrote:

> 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.
The definition used in my proof was not meant to allow manual restarting,
and the initial condition that it uses does not require any. It may be that I
have made a mistake in expressing what definition I was using, but in this
case that's easy to fix simply by using different wording in the proof
without changing the argument.
> 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?
Again, I think you may misunderstand the proof; the initial condition in
the proof already does this. (I spend a lot of time showing this in the
proof itself.) See the extra condition on Conjecture 0 (bottom of page 3/
top of page 4 of <http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf>)
that talks about 0s in state A; the purpose of that condition is so that
the initial conditions can be strung together in such a way that the machine
does its own restarting. This is a lack of clarity in the proof which should
probably be fixed with a clearer explanation. I agree with you that if the proof
did require manual restarting, that would be a flaw in the argument rendering
the proof invalid, but that is not the case.
> 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.
My second submission for the prize was actually rejected on grounds
similar to those; my third submission was accepted on the basis that I'd
demonstrated universality to an extent sufficient for whoever was judging
it. The difference between those versions was my description of a procedure
for easily generating the initial condition using nothing but a sequence of
simple steps that don't really interact with each other. Most of page 25 of the
online version of the proof explains what the procedure for extending a finite
region of the tape created at the start of the initial condition generation (which
is non-universal because it is known in advance to halt) is at the level of
system 3 (a Turing-machine-like system which is trivially equivalent to the
2,3 Turing machine in question), to produce the entire infinite initial condition;
it's obviously non-universal (to me at least) and not 'doing the calculation itself'
for at least two reasons; because it operates on separate regions of the original
tape, keeping them separate, in ways which are basically just translations,
repetitions, and padding with 1s or 2s, not paying attention to the neighbours of
such regions (and so is non-universal for the same reason that a neighbour-
independent substitution system is), and because each separate part of the cyclic
tag system maps to a different part of the tape, ensuring that the initial condition
is not itself doing the calculation because no part of it has enough information to
be able to simulate even a single step of the calculation. My third submission
was basically devoted to making this as clear as possible.
> 
> 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.
This is an obviously non-universal method of initialising the tape; there are
others, and I would argue (and have been arguing) that the method given in
the proof is such a non-universal method. I agree, it is a nice puzzle and a good
question which really gets to the root of the matter.
> 
> Vaughan
-- 
Alex Smith