[FOM] Simple Turing machines, Universality, Encodings, etc.

[Todd Rowland]

The issue mentioned by Vaughan Pratt was, in fact, one of the central 
points of discussion during the judging of the Wolfram 2,3 Turing Machine 
Research Prize.

When Minsky posed the question of finding the smallest universal Turing 
machines in 1967 [1], he restricted the problem to Turing machines with 
finite initial conditions.  Indeed, arbitrary infinite (but 
non-computable) initial conditions can allow a machine to solve the 
halting problem and perform other miraculous computations that are 
seemingly impossible in our physical universe.  Clearly, Minsky was 
justified in forbidding arbitrary infinite initial conditions.

But later researchers, namely [2], noted that although arbitrary infinite 
initial conditions should not be allowed, that interesting results could 
be obtained if Minsky's restrictive definition of a 'universal Turing 
machine' were relaxed to allow repetitive infinite initial conditions. 
This relaxing of the restriction on a Turing machine's initial condition 
generalizes the definition of a universal Turing machine, and allows 
machines that were previously non-universal to be considered universal.

Of course, once one allows repetitive infinite initial conditions, one is 
compelled to ask what sort of non-repetitive infinite initial conditions 
might be allowable.  Again, one does not want to allow arbitrary infinite 
initial conditions, since trivial machines would become universal, but how 
far can one relax the restriction on initial conditions, and still retain 
a reasonable definition of a universality?

>> The non-finitary system is evidently universal, and the program 
>> performing the concatenation is equally evidently non-universal. Smith 
>> infers from this that the machine checking each of the concatenated 
>> initial conditions in turn must be universal.

Alex Smith did not only show that the encoding of the initial condition is 
non-universal.  He showed that the encoding is very computationally weak and 
then concludes that the Turing machine is universal in a generalized sense.

>> The analogous argument for numbers in place of machines and "infinite" 
>> in place of "universal" would be, if x+y is infinite and y is finite 
>> then x must be infinite.

This is an inappropriate analogy because it does work for numbers.  More 
to the point is that there are no interacting systems here, just a simple 
function that computes the initial configuration, then the Turing machine 
runs on its own.

Smith's use of non-repetitive infinite initial conditions is 
controversial, but is a natural extension of current definitions which 
allow infinite repetitive initial conditions.  We hope that the ensuing 
discussion will enrich debate in the scientific community concerning the 
nature of computational universality.

Whenever a generalization of the definition of a universal Turing machine 
is put forward, then the status of some machines will necessarily change 
from 'non-universal' to 'universal'.  It is a challenge to explicitly 
construct a machine with initial conditions similar in spirit to Smith's, 
that is obviously too simple to be considered universal, and which is 
performing a universal computation with those infinite initial conditions.


[1] Marvin Minsky, Computation: Finite And Infinite Machines,
Prentice-Hall, Englewood Cliffs, 1967

[2] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal 
Turing machines. Journal of ACM, 8(4):476-483, October 1961.