[FOM] Is Wolfram and Cook's (2, 5) Turing machine really universal?
JoeShipman at aol.com
Thu Sep 13 11:57:04 EDT 2012
Yes, but the point of the original question is that the (2,5) machine is not only weakly universal, but universal for inputs on ordinary non-patterned blank tape.
Sent from my iPhone
On Sep 13, 2012, at 3:22 AM, Matthew Cook <cook at vigeland.paradise.caltech.edu> wrote:
> On Sep 9, 2012, at 10:48 AM, Dominic Hughes wrote:
>> Is Wolfram and Cook's (2,5) Turing machine really universal?
> To see the (2,5) Turing machine (from my 2004 paper) computing the standard Rule 110 ether, start it at the middle of
> (0² 0 1 0)* 0² (≠ ≠ 0 1² 0 0²)*
> Where (...)* means infinite repetition.
> The much longer patterns needed for the Rule 110 construction translate into longer periodic patterns for the left and right of the TM's starting tape, but the way the machine does its sweeps across the tape is identical.
> These machines operate in a very simple way and were examined by others long ago, for example David Eppstein even improved one of the machines in 1998, as noted in the paper.
> In "A Concrete View of Rule 110 Computation", http://arxiv.org/abs/0906.3248v1, section 1.6 and figure 3 give a slightly improved version of this machine.
> But this machine is obsolete anyway! Even smaller TMs have been found since then; see Neary and Woods, "Small weakly universal Turing machines", http://arxiv.org/abs/0707.4489, which gives a 2 state 4 symbol universal machine and also shows in detail how these TMs operate. The overall idea of alternating sweeps is the same in all of these machines, but they differ in the mechanics of the CA update.
> You can see the machine in action using a TM simulator, such as this nice one I just found via Google:
> ==== (snip) program ====
> 0 0 0 R 0 ; We use state 0 (the starting state)
> 0 1 1 R 0 ; to find the middle of the tape, where
> 0 - - R 0 ; our machine should start.
> 0 ≠ ≠ L Se ; Then we start our machine in state Se.
> Se 0 - L Se ; We use - for 0² and + for 1² because this
> So 0 ≠ L Se ; simulator requires single character symbols.
> Se 1 ≠ L So
> So 1 + L So
> Se - 0 R Se
> So - 0 R Se
> Se + 0 R Se
> So + 1 R Se
> Se ≠ 1 R So
> So ≠ 1 R So
> ==== (snip) initial tape ====
> ==== (snip) enter both of those and press "run" ====
> FOM mailing list
> FOM at cs.nyu.edu
More information about the FOM