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

[Damien Woods]

Let me clarify something.

 > > 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 blanktape.
 >
 > On 9/13/12 5:26 PM, Damien Woods wrote:
 > 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.

When I wrote the latter sentence, I was actually thinking about a more general question than Joe 
Shipman's, i.e. the following. It would be very interesting to prove that, on a standard tape with a 
blank symbol, either (a) all (2,5) machines are not universal (in some well-defined sense, a 
crucially important caveat), or (b) there is such a universal (2,5) machine.

As to Joe Shipman's actual question: It could well be the case that the particular (2,5) machine in 
question does not compute much when using a tape with a standard blank symbol, but maybe this would 
not be so interesting as the machine was not designed to work in this fashion! However, the more 
general question about the kind of universality that (2,5) machines are capable of is interesting.


Damien



On 9/13/12 5:26 PM, Damien Woods wrote:
> 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
>>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom