[FOM] Is Wolfram and Cook's (2, 5) Turing machine really universal?

[Matthew Cook]

On Sep 9, 2012, at 10:48 AM, Dominic Hughes wrote:
>  Is Wolfram and Cook's (2,5) Turing machine really universal?
>  http://arxiv.org/abs/1208.6342


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.

Matthew


P.S.
You can see the machine in action using a TM simulator, such as this nice one I just found via Google:

http://morphett.info/turing/turing.html

==== (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 ====
-010-010-010-010-010-010-010-010-≠≠0+0-≠≠0+0-≠≠0+0-≠≠0+0-
==== (snip) enter both of those and press "run" ====