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

[Matthew Cook]

On Sep 13, 2012, at 5:57 PM, 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.

No, there is no proof (or claim thereof) of strong universality or intrinsic universality for Rule 110 or for any of the TMs that emulate it.

strong = only a finite portion of the tape is non-blank.
weak = an infinite portion of the tape is non-blank (no notion of "blank symbol").
intrinsic universality = the entire infinite state of an arbitrary CA can be updated in parallel by the intrinsically universal CA (TMs can't do this).

So far as I can tell, the issue being addressed (in the arXiv paper [1] starting the thread) has to do with interpreting Wolfram's presentation [2] as only demonstrating strong emulatability of Rule 110 by the TM in question, whereas weak emulatability is clearly needed to prove universality of the TM.  My previous mail showed that weak emulation is straightforward.

The smallest weakly universal TMs I know of are given in [3].

The smallest strongly universal TMs I know of are as listed in figure 1 of [4].

The smallest intrinsically universal CA that I know of is given in [5].

Matthew

[1] Hughes, "Is Wolfram and Cook's (2,5) Turing machine really universal?", 2007, http://arxiv.org/abs/1208.6342
[2] Wolfram, "A New Kind of Science", 2002.
[3] Neary and Woods, "Small weakly universal Turing machines", 2007, http://arxiv.org/abs/0707.4489
[4] Neary and Woods, "The complexity of small universal Turing machines: a survey", 2011, http://arxiv.org/abs/1110.2230
[5] Ollinger and Richard, "A Particular Universal Cellular Automaton", 2008, http://arxiv.org/abs/0906.3227