[FOM] Simplest universal Turing machine
Vaughan Pratt
pratt at cs.stanford.edu
Sat Oct 27 12:25:49 EDT 2007
Meanwhile I see that the definition of universality for the subject 2,3
machine that I gave in my previous message,
> In this case it should be reasonable to
> require as the criterion for universality of a machine T that there
> exist an r.e.-complete set K of suitably delimited strings over the
> three-letter alphabet of the tape and a recursive set H of finite
> sequences of configurations of T such that when T is started on word w
> so delimited, w is in K if and only if an initial segment of the
> resulting configurations of T is in H.
admits Alex Smith's solution. This would be good news for the solution
were it not for the fact that my definition suffers from the same
vulnerability as I pointed out for his solution.
In particular let T be a nondeterministic PDA and H a PDA, say
deterministic for simplicity (but nondeterministic still keeps H
nonuniversal so either will do). T uses its stack as the left hand half
of a Turing machine tape and guesses H's control state at every step.
H's job is to manage the right hand half of the tape, confirm T's guess
at each step, and indicate acceptance of T's computations on w when
those together with H's work indicate membership of w in K.
The resulting team implements a nondeterministic Turing machine
accepting K which is therefore universal, K being r.e.-complete (=
c.e.-complete to use the dumbed-down terminology, = complete to use the
BC terminology, Before Cook).
Here's a suggested fix. Require that the set H be not just recursive
but of complexity (say nondeterministic space to sound generous) a
recursive function of the length of w. This should suffice to make H
not just a judge of Halting but an Honest one, by giving it lots of
resources for analyzing T's thought processes but not enough to team up
with T to contribute to the solution.
The question then arises as to whether Smith's solution passes this
stronger test. It seems to me that it doesn't, because Smith's encoder
although not universal keeps track of the running time, which can grow
without limit when w is not in K, obliging the encoder to use more
storage than any recursive function of the length of w.
Perhaps WRI has some definition of intermediate strength between my
obviously flawed one and my slightly stronger one, that on the one hand
admits Smith's solution while on the other is demonstrably immune to the
sort of problem plaguing weaker criteria for universality.
In any event it would be nice to understand in exactly what sense WRI
considers this 2,3 machine to be universal, which as I understand the
original problem was left to the committee to determine. I seem to be
only the n-th person to raise this question---I hope I've raised it
sufficiently sharply here as to indicate either the continuing
difficulties or my continuing confusion.
Vaughan Pratt
More information about the FOM
mailing list