[FOM] Simple Turing machines, Universality, Encodings, etc.
Todd Rowland
rowland at wolfram.com
Mon Oct 29 22:48:29 EDT 2007
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.
More information about the FOM
mailing list