[FOM] Simplest universal Turing machine

[joeshipman@aol.com]

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