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

[Alexander Smith]

(I subscribed to this list after the message I'm replying to was sent, which means that this message will probably show up as a new thread; I'm replying to the quoted message by Vaughan Pratt pratt at cs.stanford.edu.)

Vaughan Pratt wrote:

> 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.

There is a mistake in your reasoning at this point: the linear-bounded-automaton+preprocessor system that you suggest here is not 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' is false; a universal machine is capable of infinite searches where the existence and value of any answer searched for is not known in advance. For instance, a universal machine can search for counterexamples to the Riemann hypothesis; the linear-bounded-automata+preprocessor system cannot, unless the preprocessor itself is sufficiently advanced to search for a counterexample itself to know how large the numbers can get before a counterexample can be found. (It would be possible to do this for the specific case of the Riemann hypothesis - or any other specific case - by engineering a specific preprocessor for the exact problem at hand, but this does not work in the general case.) Likewise, a system consisting of one push-down automaton is not universal, not even with a preprocessor that's a push-down automaton itself, due to the fact that information can only be sent one way (from the preprocessor to the main system), and therefore push-down automata are not universal by this definition, even though systems that are like push-down automata except with two memory stacks (this is one way of interpreting Boehm's system P'', for instance) are universal.

The definition of universality used is important in the situation in question; the problem of what sorts of initial conditions are allowed is a tricky one. There seems to be a lemma in question, which is that if a sequence of systems, each of which reads input and produces output, are set up so that each one reads the output of the previous one, and none of them are universal, then the resulting system cannot be universal. In the case of the prize problem, this lemma was basically incorporated into the definition of universality. (The technical details of the original problem specified 'One common definition requires that the encoding of input for the universal system, and the decoding of its output, must both be done by a computation that always halts after a finite number of steps. One difficulty with this definition is that it may be too restrictive for infinite tapes. It is not clear, for instance, whether one should allow a Thue-Morse sequence <http://www.wolframscience.com/nksonline/page-890>  in the initial conditions.'; the definition that was used in the prize basically said that what was required was that the encoding of the initial condition could be infinite but had to be done in an obviously non-universal way, and given this definition the lemma in question is trivial.) To prove or disprove this lemma for a different definition, it is necessary to first define 'universal' in a way which uses a different treatment of the way initial conditions are handled; it may well be that it is true with some definitions of 'universal' and false with others; in this case the situation would be that in the absence of the clarifications of the meaning of the problem that were decided upon by the committee that decided the outcome of the Wolfram 2,3 Turing Machine Research Prize, the problem of deciding whether the machine in question is universal would be ambiguous (but these clarifications were given and decided upon, so any ambiguity was resolved in this case).

In any event, the construction of the initial condition is done in a highly computationally simple manner, making it intuitively reasonable that the system is universal; from my point of view, a definition of universality that excludes this sort of initial condition would be inconsistent with an intuitive view of what universality is.

> 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?
> 
> Vaughan Pratt

-- 

Alex Smith

Wolfram 2,3 Turing Machine Research Prize winner