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

[Damien Woods]

Hi,

On 9/13/12 8:57 AM, Joe Shipman wrote:
 > 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.

This does not seem to be addressed by Dominic Hughes' writeup (e.g. see the notation in Theorem 1). 
A positive or negative answer to this question would indeed be a breakthrough.

After a quick scan of Dominic Hughes' writeup, I think it is simply giving a method to implement 
what Matthew Cook described in his previous email.

Damien


On 9/13/12 8:57 AM, Joe Shipman wrote:
> 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.
>
> -- JS
>
> 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?
>>> 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" ====
>>
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/listinfo/fom
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>