[FOM] Definition of universal Turing machine
joeshipman at aol.com
Sat Oct 27 13:36:07 EDT 2007
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
> >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
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.
Email and AIM finally together. You've gotta check out free AOL Mail! -
More information about the FOM