[FOM] 2,3 Turing machine proof controversy

[TURLOUGH NEARY]

On Sat, 10 Nov 2007 14:04:23 Bob Hearn wrote:

> If we agree that the above are not problems, and the
> (2, 3) machine  should be called universal, is it
> meaningful to refer to it, as Wolfram  does, as "the
> smallest universal Turing machine that exists"? There
> are  many kinds of computation machine. It seems to me
> that to compete in a  game of minimizing states *
> symbols, for a result to be meaningful there  must be an
> established definition of what kind of machine one is
> using.

You make an excellent point which has also been noted before
by people who have published in the area of small universal
Turing machines. I can see no sense in which it is true to
say that Alex Smith's machine is the smallest universal
Turing machine. Of course I would say congratulations to
Alex Smith for creating
an interesting construction and indeed a new type of
encoding.

To further illustrate the above point consider the small
universal Turing machine with 2 states and 3 symbols from
Kleine-Buning and Ottmann (see ref [1] below). Their machine
is a restriction on Alex Smith's machine in the following
sense

1. Only 5 of the 6 available instructions are used
2. The Turing machine does not change any symbol on its tape
(i.e. for each instruction the read symbol is the same as
the write symbol, could in fact be considered an non-writing
machine)	
3. The blank tape is periodic


The machine of Kleine-Buning and Ottmann is a generalisation
in the sense that its tape is 2-dimensional.

In addition to the above the machine of Kleine-Buning
and Ottmann halts when it is finished a computation.

Neither the machines of Smith nor Kleine-Buning and Ottmann
fit the more well-known classical definition of the Turing
machine. An objection that can be made to Kleine-Buning and
Ottmann's machine is that using a 2-dimensional tape is
unreasonable. In my opinion this is a much less a
contentious issue than Smith's (interesting) encoding.

So which machine is the smallest? Unless it has been shown
how you trade states and symbols for tape dimensions, and
how you trade Smith's non-periodic initial conditions for
periodic initial conditions, I do not see how the statement
can be made that Smith's machine is the smallest universal
Turing machine.

Alex Smith's machine may well be the smallest machine of its
kind, but it is misleading to call it the smallest universal
Turing machine.

Another related point to note: 
The following is a quote from Wolfram's blog dated October
24th: 

“There were some simpler universal Turing machines
constructed in the mid-1900s--the record being a 7-state,
4-color machine from 1962.
That record stood for 40 years--until in 2002 I gave a 2,5
universal machine in A New Kind of Science.”

The 2-state and 5-symbol machine uses an infinite periodic
background to function (unlike Minsky's more conventional
Turing machine). As these machines are incomparable it is
untrue to say a record was broken. On the other hand if we
allow
superficial comparisons between different models then
choosing to compare the 2-state, 5-symbol machine with
Minsky's machine and not the “record holding” 2-state,
3-symbol universal Turing of Kleine-Buning and Ottmann seems
strange.

[1] Hans Kleine-Buning and Thomas Ottmann. Kleine
universelle mehrdimensionale Turingmaschinen. Elektronische
Informationsverarbeitung und Kybernetik, 13(4-5):179-201,
1977.

We do think Alex Smith's result is interesting and seems to
involve quite a bit of ingenuity. However in some places we
believe the result has been misrepresented.

As researchers in the field of small universal Turing
machines we take the view that there are many models that
are directly inspired by Turing machines, but one must
always be very clear about exactly what claims are being
made and with respect to what model. If we all try to stick
to this convention, and clearly set our results within the
context of work done by others, then many controversies will
simply disappear.

Turlough Neary
Damien Woods