[FOM] Smallest universal machine
pratt at cs.stanford.edu
Fri Oct 26 21:05:27 EDT 2007
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
"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.
More information about the FOM