How is the rule 110 Turing complete?

Question

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'?

Answer 1

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.

Answer 2

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.