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

[Dominic Hughes]

Thanks for your responses.  Given recent comments, I should clarify my
question:

 (1) The draft http://arxiv.org/abs/1208.6342 set out to prove, for the
     first time, that the (2,5) machine is (weakly) universal.  It showed
     that a rather intricate construction must be introduced to achieve
     this, the 'wrap construction'.

 (2) Neither Wolfram nor Cook offered any equivalent construction, let
     alone a proof of (weak) universality.  [Details below.]

 (3) My question: is it worth me investing the effort to finish the paper
     on the wrap construction, hence prove that the (2,5) machine is
     (weakly) universal?

My fear is that I'll waste vast amounts of additional time on something
that no one ends up caring about, because most people don't realize that
the (2,5) machine was never (and still hasn't been) proven (weakly)
universal.

It's actually very easy to explain why (weak) universality was never
proven for the Wolfram-Cook (2,5) machine (even after Cook (2009)), and
for that matter for the (2,4), (3,3) and (6,2) machines of Neary and Woods
(2007):

 (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).  The wrap construction precisely
fills this gap, and its intricacy witnesses how vast this gap really is.

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).

Dominic

P.S.  A personal/diplomatic note.  I find the small Turing machines in the
works of Wolfram, Cook, Neary and Woods to be *extremely* elegant.
Please don't interpret my observation of missing proofs as a lack of
appreciation for the papers, the authors or their machines.  On the
contrary, I deeply value these works --- so much so that, after all, I was
inspired enough to spend months writing a paper on the subject back in the
spring of 2007!  Please don't think that I'm trying to stir the pot by
highlighting the missing proofs and attempting to bridge them with a new
construction --- I'm simply driven by a fundamental desire to reach an
elegant truth, just like anyone else.

P.P.S. Here are further details on the lack of a (weak) universality proof
in the literature.  Wolfram (p.707, 2002) only presents an example run an
infinite zero background.  Cook (p.4, 2004) just quotes the 2-by-5 table
defining the machine.  Cook's update (2009) only gives an example run on
the background ether (see (a) in the main text above).  Neary and Woods
(2007) also only give example runs for their three machines on the
background ether.

References

Wolfram 2002.  A New Kind of Science.

Cook 2004.  Universality in Elementary Cellular Automata.
Complex Systems, vol. 15 (1), 2004, pp. 1-40.

Neary & Woods 2007. Small weakly universal Turing machines.
http://arxiv.org/abs/0707.4489

Cook 2009.  A Concrete View of Rule 110 Computation.
EPTCS 1.  http://arxiv.org/abs/0906.3248



On Sun, 9 Sep 2012, Dominic Hughes wrote:

> Stimulated by a recent question of Bob Solovay about universality, I dug
> out an unfinished draft from five years ago and placed it on the arxiv,
> warts and all:
>
>   Is Wolfram and Cook's (2,5) Turing machine really universal?
>   http://arxiv.org/abs/1208.6342
>
> Is this paper worth finishing?  I'm extremely busy outside of academia
> these days, so I'd like to be sure I'm not wasting my time.  FOM seemed
> like the perfect community from which to canvas opinion.
>
> Dominic
>
> P.S. Abstract:
>
> Wolfram [2, p. 707] and Cook [1, p. 3] claim to prove that a (2,5) Turing
> machine (2 states, 5 symbols) is universal, via a universal cellular
> automaton known as Rule 110. The first part of this paper points out a
> critical gap in their argument. The second part bridges the gap, thereby
> giving what appears to be the first proof of universality.
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>

http://boole.stanford.edu/~dominic