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

[Matthew Cook]

> (a) The authors only provide an example run of a simulation on the
>    so-called "ether" of Rule 110.
> 
> (b) One must provide a construction which simulates Rule 110 on initial
>    states with periodic words induced by the underlying cyclic tag
>    system.
> 
> There is a vast gap between (a) and (b).

Actually there is no gap, because an initial state of (b) consists of gliders traveling in the ether of (a).  That is, the initial states needed for the proof contain plenty of ether, and the TM can bounce (change direction) in these ether regions exactly as in the "pure ether" examples.

Doing this in practice is very easy.  For example, you can take the repeating word for the left hand side in Rule 110, and replace an occurrence of 10011011111000 with 100²0100²0100²0, and the result is a fine left hand word for the TM.  Hardly an intricate construction.  The right hand side is similar.

I think you are right that the simple description in Wolfram's book of how to do emulations with 0s on the right and 0²s on the left may at first appear to be insufficient for emulation with arbitrary patterns.  Wolfram probably chose this example emulation for its simplicity.  However, it turns out to be easy to extend this example to arbitrary patterns.  As I put it in one paper, "Encoding the Rule 110 initial state into an initial tape for these Turing machines is fairly direct and we will not discuss the details of these transformations."

> Hopefully the wrap construction can be tweaked to provide proofs of (weak)
> universality for the three beautiful machines conjectured to be (weakly)
> universal by Neary and Woods (2007).

I think the paper of Neary and Woods is extremely clear in demonstrating how their machines work in the weak setting and why they are universal.  I would definitely refer to their universality as proven, not conjectured.

Matthew