[FOM] Smallest universal machine

[Vaughan Pratt]

Martin Davis wrote:
> Vaughan Pratt wrote:
>  >Assuming it is indeed a universal machine, which I take it the committee
>  >is confident of, Alex Smith certainly deserves the credit for completing
>  >the argument, which of itself would appear to have been a tour de force.
> 
> As far as I know, no member of the committee has passed on the 
> validity of this 40 page proof. The determination that Smith's proof 
> is correct seems to have been made entirely by the Wolfram 
> organization. My understanding is that the I/O involves complex encodings.

Unless I've misinterpreted something, the Rules and Guidelines for the 
Wolfram 2,3 Turing Machine Research Prize seem pretty clear on the 
judging procedure:

"Submissions will be judged by the Prize Committee, and all decisions 
will be final and binding upon all participants. In the event of a tie 
or other unexpected event, the Prize Committee will make a discretionary 
decision consistent with the goals and purpose of the Prize."

This raises several interesting questions.

1.  If the prize-winning submission has not been so judged, how was a 
decision possible under those rules?

2.  What is the likelihood that an organization that seems unable to 
follow its own straightforward rules can reliably follow the far more 
complex rules of the simulations given in the 40-page submission?

3.  In the hypothetical situation that someone subsequently satisfies 
the committee that this Turing machine has a decidable halting problem, 
what would be the contractual and/or moral obligations of WRI and 
Wolfram as the joint offerors of the prize?  In what sense would this 
count as an "unexpected event?"  Unexpected by whom?

4.  On the technical question as to the definition of "universality," it 
is customary at the "low" end to call a machine universal just when it 
has an undecidable halting problem, i.e. when there is no algorithm 
capable of predicting for a given tape configuration whether the machine 
will halt when started in that configuration.

The case of counter machines (as opposed to Turing machines, which have 
a two-way writable tape) nicely illustrates the care needed here.  A 
counter machine with two counters has an undecidable halting problem, 
which might lead one to think that for any recursive function f there 
exists a two-counter machine which when started in the configuration 
(n,0) halts in the configuration (f(n),0).  While this is true for 
three-counter machines (starting *mutatis mutandis* with (n,0,0) and 
ending with (f(n),0,0)), Frances Yao showed in the early 1970s that it 
is false for two-counter machines.  The problem is that although a 
two-counter machine can produce a suitable encoding of f(n), two 
counters are insufficient to decode the encoded result.

It follows that had the definition of "universal" been worded so as to 
entail the ability to compute any recursive function with any prescribed 
recursive encoding thereof (e.g. binary notation), we would have ruled 
out two-counter machines as universal.  So at this "low" end we do need 
to stipulate the weaker requirement of merely having an undecidable 
halting problem if we are to recognize the (genuine) universality of 
such weak machines.

There is however a further problem, in the case of Turing machines with 
only two states, that it is impractical to dedicate one of those states 
to the indication of halting.  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.  In other words T gets to think 
about w, with the goal of "concluding" in a finite amount of time as 
judged by criterion H applied to its thinking, that w is in K.  If w is 
not in K, T's only obligation is to avoid any announcement "by" H that T 
thinks w is in K, and is permitted to run forever.   For concreteness 
think of K as the set of initial configurations (state and tape) 
starting from which some given Turing machine M halts, and H as an 
observer judging whether T is simulating M well enough to "realize" (in 
a possibly deep sense that is nevertheless understood by H) that M has 
halted when it has, and furthermore T does not signal halting in this 
way in those cases where it is premature for T to judge M as having halted.

If the committee has a better criterion of universality that it's in 
agreement on I'd be all in favor of using that instead, while pointing 
out however that two states does call for some adjustment to the more 
conventional notions of universality.

5.  On the question of the paper itself, the table of contents, which is 
essential to following the dozens of cross-references in the paper, is 
useless.  First the pages print without page numbers.  Second the TOC 
gradually drifts out of sync with the physical pages, which are up to 
page 55 at the point where the TOC is indicating to look at page 44.  I 
can't imagine anyone trying to actually read this without throwing up 
their hands after half an hour's struggling with it and sending it back 
for proper numbering.

The best I've been able to make of this paper under these trying 
conditions is that it first proves that two machines working together, 
the subject 2,3 machine and an encoder, constitute a universal team.  It 
is then shown that the encoder is not universal, from which it is 
inferred that the 2,3 machine must be universal.

Evidently I've misunderstood something, since two PDA's working together 
constitute a universal team (use the two stacks to simulate the two 
halves of the tape on either side of the head), but the fact that one of 
them is not universal does not entail the universality of the other.  No 
amount of fiddling with "weaker" definitions of universality along the 
lines I indicated above can change that fact, since both PDA's are 
equally non-universal in an entirely unambiguous way.

Vaughan Pratt