[FOM] Smallest universal machine

[Hector Zenil]

On 10/30/07, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
> Hector Zenil wrote:
> >One could fairly argue that two non-universal coupled automata can reach
>  >universality, but it would require the couple to interact at every step,
>
> Thank you, this nicely boils the fallacy down from 55 pages to two
> lines.  Merely providing an initial condition saying how long to run is
> sufficient to turn a nonuniversal machine such as an LBA into a
> universal one, without any further interaction.
>
> Vaughan Pratt


That quote is from my reply to your 10/27 post (below), in which you
were talking about pushdown automata (PDAs) interacting at every step.
My response correctly noted that was not the case in Alex Smith's
proof. You later agreed with me on your 10/30 post since you had not
considered the communication requirement between the two machines
(performed at the start, one-way and off-line in Smith's
construction).

You are now talking about linear bounded automata (LBA), changing your
first argument. As I understand it, your objection now is to the
argument that the same reasoning would prove an LBA is universal,
which you think is too generous. Merits and flaws of that objection
aside, the current objection is a substantially lesser refutation than
your initial complaint of an elementary flaw in the proof. From our
point of view, it is a contribution offered by Smith's proof to the
discussion on universality making a sound generalization of the sort
done before.


On 10/27/07, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
> 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.
>

Hector Zenil