Registered: Oct 2003
Confusion on FOM
The following was posted earlier today on the FOM mailing list.
Below it is a response that hopefully clears up the confusion.
Not wanting to push my luck I'll settle for one question.
How did an argument containing such an elementary fallacy get through the filter?
Smith gives a series of what I'll call finitary systems each of which runs the computation for a specified number of steps, each simulating its predecessor, then gives a non-finitary system (PDF page 21, Table of Contents page 19) that concatenates the initial conditions of progressively longer computations and runs one of the finitary systems on that concatenation.
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.
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 line of reasoning works for numbers but not machines. For machines it would show that a linear-bounded automaton (LBA) is universal: a non-universal machine can easily add to the input a string giving in unary the number of steps to emulate the given Turing machine, and a suitable LBA can then run the computation that far without exceeding its linear space bound.
As Chomsky showed half a century ago, linear bounded automata are not universal Turing machines.
Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?
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 , 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 , 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, 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.
 Marvin Minsky, Computation: Finite And Infinite Machines, Prentice-Hall, Englewood Cliffs, 1967
 Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of ACM, 8(4):476-483, October 1961.
Report this post to a moderator | IP: Logged