[FOM] Simplest universal Turing machine

[Vaughan Pratt]

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