[FOM] Simplest universal Turing machine
joeshipman@aol.com
joeshipman at aol.com
Thu Oct 25 13:39:53 EDT 2007
It depends on what you mean by "universal". My definition of a
"Universal TM" is
**there exists a total recursive function which takes a triple (finite
alphabet, set of quintuples of a 1-tape TM using that alphabet, initial
tape configuration) to an initial tape configuration, such that the
"Universal TM" halts if and only if the TM you build from the given
quintuples and given tape configuration halts (and both tape
configurations have the "blank" character in all but finitely many
places).**
This is equivalent to a definition where the input alphabet is assumed
to have only two characters, and where the input initial tape
configuration to be modeled is blank.
The machine referred to in this press release appears to differ in two
ways: the "initial tape configuration" is not eventually blank, and the
recognition of "halting" in the behavior of the machine being simulated
involves some property of the simulator other than its halting.
If "eventually blank" is replaced by "eventually periodic in both
directions" where the periods are very short, and the recognition of
"halting" is some property like "repeats a finite cycle of states
indefinitely while moving steadily into an eventually periodic portion
of the tape" where the cycle is very short, then it is clear that this
"2 state 3 symbol" machine can be replaced by a machine that is not
much more complicated, that satisfies the two criteria; but Wolfram
ought at least to show how much overhead (in terms of symbols, states,
or quintuples) these two requirements add.
-- JS
-----Original Message-----
From: Timothy Y. Chow <tchow at alum.mit.edu>
To: fom at cs.nyu.edu
Sent: Wed, 24 Oct 2007 8:57 pm
Subject: [FOM] Simplest universal Turing machine
I was wondering if FOM readers have any comment about Stephen Wolfram's
announcement today:
http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html
Tim
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
________________________________________________________________________
Email and AIM finally together. You've gotta check out free AOL Mail! -
http://mail.aol.com
More information about the FOM
mailing list