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

Dominic Hughes dominic at theory.stanford.edu
Sun Sep 9 13:48:31 EDT 2012

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?

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.


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.

More information about the FOM mailing list