[FOM] 2,3 Turing machine proof controversy

[joeshipman@aol.com]

Pratt:
>If the game is merely to minimize the state-symbol product, Alastair
>Hewitt's universal 3,2 machine posted at
>http://forum.wolframscience.com/showthread.php?s=1aece16e84a2f0a6cd82bb3
e0775d199&threadid=1432
>on July 24 would seem to settle this question elegantly without having
>to agonize even over nonblank backgrounds let alone restarting
>strategies.  The crucial difference between 3,2 machines and 2,3
>machines is that the latter can only carry one bit from cell to cell,
>whereas the former can carry log_2(3) = 1.58496 bits, making it that
>much harder for a 2,3 machine to simulate a universal 3,2 machine. 
(Not
>to say that it's impossible, in fact this would be how I'd go about
>trying to find a universal 2,3 machine, rather than trying to emulate
>Rule 110 directly.)


This is a very interesting construction, but it only simulates rule 110 
on a "circular tape" rather than on an arbitrarily growing tape. I like 
very much the general idea of simulating a CA rule with a TM like this, 
though, and it can be converted into a (4,3) machine that does an 
honest simulation by adding 1 symbol for "end of finite input" and 1 
state for "have seen end of finite input, moving backwards until the 
other end is encountered".

This does not QUITE show that that (4,3) machine is "universal" 
according to the TRADITIONAL definition, because of the complexities in 
defining what it means for rule 110 to be "Universal", but I suspect 
one would not need much more complexity in the TM to get one which was 
universal in the traditional sense of "set of finite inputs for which 
'halt' occurs is r.e. complete".

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