[FOM] Smallest universal machine

[Hector Zenil]

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


1. Concerning the prize committee, we did not expect them to go
through the details of the proof but to support the reviewers on
technical issues related to their fields of expertise. We would have
been delighted to have had them spend more time on the proof but that
wasn't our expectation. We did talk to people about how to set the
prize up. Basically we needed judgement about their areas and we were
very careful to cover those that could come up in a universality
proof. We are grateful to the committee for covering those areas and
we are happy that they were more active than many such committees.

In the review process, committee members agreed with the Wolfram
Science internal reviewers, while others asked for additional
clarifications (such as fulfilling universality basic requirements for
non-halting machines). All committee members had Alex Smith's proof in
hand for a couple of months. But it was Wolfram staff who did the hard
work to achieve a satisfactory level of verification (between
revisions and revision requests), and we thought that by waiting any
longer we would not have learned more. It helped that a lot of the
proof was submitted in the form of programs that could be run and
analyzed in a systematic way.
Smith's proof is available to everybody, anyone can point out
anything, and it is nice to get the sense that there are people out
there who would be interested in verifying proofs. This is great news,
and if we do other prizes we would definitely like to take advantage
of that. We would be also delighted to hear opinions on how to set up
next prizes.

2. Concerning the definition of universality, a halting state or
halting instruction wasn't a requirement. This is a common usage
nowadays in the field of small universal Turing machines (see detailed
references below), which is a generalization of previous definitions.
If there is no clear definition is because there is no clear-cut,
established procedure to determine when an initial condition is
computationally simple enough to be acceptable. Some would wish
universal computation stick to a finite initial condition with an
unbounded tape filled with "blanks", because that's the only case
where the theory is entirely clear. However, others accept
generalizations such as periodic "blank" words as long as they remain
computationally simple enough (possibly generated in the same fashion
as an unbounded "blank" tape). So Alex Smith's use of a non-periodic
but still sufficiently computationally simple background is a natural
generalization of this sort. The key point is that the background can
be set up without doing universal computation, so the 2,3 machine
itself actually carries out the computation.
One could fairly argue that two non-universal coupled automata can
reach universality, but it would require the couple to interact at
every step, as in Margenstern's nice example [1], but that's very
different from a non-universal second automaton intervening only once
at the first step.

We are glad that this is making a contribution to the discussion on
universality. We expect that others will further clarify what Alex
Smith has done. We particularly hope that his methods can be extended
to other similar proofs.

3. On the question of the paper itself, the final version of Smith's
proof will be published in the Complex Systems journal as announced in
the prize rules and guidelines. The proof currently available on the
website is Smith's prize submission:
http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf
I am certain that the journal version will have a better format and
further clarifications after the peer reviewing.


[1] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal
number of instructions for universality of Turing machines connected
with a finite automaton. International Journal of Algebra and
Computation, 13(2):133–202, April 2003.


Extract from the prize website FAQ's about the universality definition:
http://www.wolframscience.com/prizes/tm23/faqs.html
--
Does your Turing machine halt?
No. Like most real computers, it
doesn't have a halt state; it just keeps computing forever. "Results"
can get "read off" when the machine "says" it's ready by exhibiting
some predefined behavior.

What definition of universality are you using?
The standard one appropriate for unbounded computations. It's the
same as in the NKS book. See Technical Details:
http://www.wolframscience.com/prizes/tm23/technicaldetails.html

Is there a halting problem for the prize Turing machine?
The machine does not have a halt state, but there are analogs of the
halting problem that ask whether the machine achieves particular
configurations. Showing that any such problem is undecidable is
tantamount to proving universality, but does not strictly achieve
this.
----


Hector Zenil


----
Hector Zenil-Chavez
hector.zenil-chavez at malix.univ-paris1.fr
http://zenil.mathrix.org
Université Pantheon-Sorbonne -Paris 1- (IHPST)
Université de Lille I (Laboratoire d'Informatique Fondamentale de Lille)
--------------------------------
Fondation Suisse
Cité Internationale Universitaire de Paris
7, bd Jourdan
75014 Paris
France
--------------------------------------------------------------