# How is the rule 110 Turing complete?

I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0).

I've just read they're Turing complete, but I can't even fathom how would you 'program' in 'rule 110'?

• It's actually rule 110, not rule 101. The proof is outlined on the wikipedia page though it's note entirely obvious how the text makes the connection to the proof. – Wolfgang Bangerth Sep 22 '12 at 0:06
• @WolfgangBangerth thanks for that, I've fixed it. If the proof/way to program is in there it's not obvious enough for me to spot it, sorry. – Pureferret Sep 22 '12 at 0:09
• The same question occurred to me too, if there is a script to convert a simple program into this automata somehow, and then some "simulator" to execute it. – Ondřej Čertík Sep 23 '12 at 17:14
• excellent question. the details are complex and contained in scientific papers. see tcs.SE, initial conditions for rule 110 for a sketch & some refs. basically there is a way to convert or compile a TM to a "tag system" (known to be TM complete) and then compile a "tag system" into rule 110. it would be "way cool" if actual implementations have been built for ppl to experiment with (& surely lead to new insight/ discoveries) but unfortunately, none seem to exist, or authors do not publish their code. – vzn Sep 28 '12 at 15:01
• closely related are 2d cellular automata & they can be studied for some intuitions into the 1d case. its been known since the 70s or so due to proof by Conway that "the game of life" is Turing complete. see eg Paul Rendell TM simulator in Game of Life for a modern/graphical version. – vzn Sep 28 '12 at 15:11

Universality is a somewhat informal notion. What it roughly means is that for each computable function $f$ there is a "program" $P$ in the model so that "running" $P$ on any input $x$ always "halts", and "outputs" the correct answer. (Note that Turing machines don't make an appearance here: they are just one example of a universal computation model.)

The quoted words are those that need to be defined. For Turing machines:

• A program is specified as a list of states, a tape alphabet, an initial state, final states, and transitions.
• Running a Turing machine $T$ on an input $x$ means that we initialize the tape with an encoding of $x$ and run the machine $T$ on this tape according to the usual rules.
• A Turing machine halts if it reaches a final state. (There are some variants here.)
• What the Turing machine outputs (if it halts) is the contents of the tape.

Rule 110, as a computation model, needs to be defined formally in the same way. A definition is reasonable if one can computably simulate the computation model, in the following sense: there is a computable function $S$ such that for every program $P$ and input $x$ (both encoded as natural numbers), $S(P,x)$ halts iff $P$ halts on $x$, and if $S(p,x)$ halts then its output is identical to the output of $P$ on $x$.

If you're curious as to the particular setup of Rule 110 as a computing system, I suggest you take a look at Matthew Cook's paper which proves the universality of Rule 110 (or rather, of a computing system built around Rule 110).

As for other rules, such as Rule 30 and Rule 90, we don't know that they are not universal. There might be convincing computing systems built around them which is universal, but we are just not aware of any.

• All true, but rule 110 doesn't have a way of halting.. It can only compute things, but not halt. – Pavel May 11 '16 at 10:21
• @Pavel It is not required to halt to be Turing-Complete – MilkyWay90 Feb 5 '19 at 17:45
• @Pavel it's always possible to emulate halting by doing a certain infinite loop. – Xwtek Mar 4 at 3:11

From Matthew's proof:

The approach taken here is not to design a new cellular automaton, but to take the very simplest one that naturally exhibits complex behav- ior, and see if we can find within that complex behavior a way to make it do what we want. We will not concern ourselves directly with the lookup table given above, but instead we will look at the behavior that is naturally exhibited by the action of the automaton over time.

The author first starts by proving that a "tag system" that removes 2 symbols at each step is universal by compiling a 2-state turing machine program. After that, he proves that a glider system can indeed implement a tag system. It is a step by step process. Then, he studies the space time of CA-110 to find the gliders and asociate them to the glider system correctly.

Now, for your question: how would you 'program' in 'rule 110'?

1. Look for the simplest 2-state turing machine and find the tapes of the basic operations OR,AND,XOR,NOT.

2. Compile them to the tag system.

3. Compile the tag-system's implementation into the glider implementation.

4. Adapt it to the CA-110 gliders correctly and you have the basic operations in a cellular automata.

Steps 1 to 4 are performed only once. From there, computing $1+1=2$ reduces to sum numbers using logic gates.

A note aside. Gliders are very special structures. The operations will be seen as particles moving and colliding (the gliders), generating different output depending on how this gliders start from or collide.

• So two glidders might 'encode' a + and when they collide I get 2? – Pureferret Sep 28 '12 at 15:47
• more precisely, multiple pairs of gliders would encode a '+' assuming that a pair of gliders can encode an OR, AND, XOR or NOT. Also consider that the numbers will probably be represented as a sequence of bits and the sum will be performed using logic gates on each pair of bits. – labotsirc Sep 28 '12 at 15:48
• caveat, there is some controversy over the rule 110 TM completeness proof in the CS community for misc reasons. one apparently is that the input condition on the CA requires infinitely periodic (but repetitive) patterns. – vzn Sep 28 '12 at 16:03
• i agree with you vzn on the controversy. Personally i dont know what to think in terms of rejecting the theoretical solution by formal means or to accept CA-110 as a superset that happens to work as a turing machine (the fact that CA are spaces of computation that work as dynamical systems and on top of that work in parallel makes me wonder if they represent a synthetic universe in progress). – labotsirc Sep 28 '12 at 16:27
• I'm not a fan of ignoring actual space and time constraints. Wikipedia cites P-completeness of cellular automaton Rule 110, and explains that Neary and Woods avoided an exponential time overhead by avoid using 2-tag systems. However, Neary and Woods later in the same year (2006) showed that even 2-tag systems don't have an exponential time overhead for simulating Turing machines. – Thomas Klimpel Apr 5 '16 at 8:42