[FOM] Definition of universal Turing machine

[joeshipman@aol.com]

-----Original Message-----
From: Martin Davis <martin at eipye.com>
>Vaughan Pratt wrote:
> >On the technical question as to the definition of "universality," it
> >is customary at the "low" end to call a machine universal just when 
it
> >has an undecidable halting problem,
>
>That's a bad "custom". At the least one would require that the
>halting set be Turing complete, i.e. of Turing degree 0'.

I think the definition "has a halting set of Turing degree 0' " is 
equivalent to the definition I gave earlier.

However, there are two ways in which the Wolfram Prize (2,3) machine 
may not fit this definition according to the few details on the Wolfram 
press release.

First of all, it appears that the initial tape configuration may not be 
"blank almost everywhere" -- it is either eventually periodic, or else 
the segments to the left and right of the initial starting square are 
intialized with different colors (Wolfram is not explicit about this 
but it can be gleaned from his doorstop "A New Kind of Science").

Second, the simulation of encoded computations performed by the machine 
may involve detecting halting in the simulated machine by some 
condition other than halting in the "universal" simulating machine, in 
which case the actual HALTING set of the simulating machine need not be 
nonrecursive (although more complex questions about its behavior, such 
as whether it ever experiences a particular partial configuration, may 
be nonrecursive). A 2-state 3-symbol machine need not "waste" a whole 
state on halting, just a single state-symbol pair.

If the "halt" state is not one of the 2 states, BUT one of the 2 states 
enters the "halt" state upon encountering one of the 3 symbols, then 
the machine is technically a 3-state 3-symbol TM, but this is not 
really a problem because one is allowed to use the convention that a 
missing state-symbol pair corresponds to halting, so by taking out that 
"quintuple" one is left with a 2-state 3-symbol machine with only 5 
quintuples instead of 6.

 From the description given of Wolfram's machine, I don't believe that 
this is what the machine is doing, and in fact it looks like the 
machine never "halts" in the conventional sense. The way one tells that 
the machine is "finished" with a simulation, in other words that the 
*simulated machine* halts, appears to be by recognizing that the 
machine has entered a certain periodic sequence of states, during which 
it moves steadily into a previously unused region of the tape (so that 
at the end of the periodic cycle, the configuration of the tape is like 
it was at the beginning of the cycle except for a shift with a specific 
finite change in the tape).

I may be wrong here because I can't find all the necessary information 
about how the simulation works. Can someone on the committee please 
confirm or correct my analysis?

Anyway, if I am right, then converting the purported "universal" 
machine into one whose actual halting set is Turing complete will 
involve defining a machine with more states or more symbols, and 
Wolfram owes us an explanation of how much "overhead" is actually 
necessitated by the requirement that the *halting set* of the 
"universal" machine be Turing complete.

-- JS
________________________________________________________________________
Email and AIM finally together. You've gotta check out free AOL Mail! - 
http://mail.aol.com