# Proving Turing Completeness by Simulating Rule 110

Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial state the next state in the evolution. Only then did I realise that this is an obviously finite process (because it's a primitive recursive function, I suppose?).

So my question is: what, involving Rule 110, would one have to simulate to prove Turing-completeness of some formalism? I thought initially a function that takes a predicate and an initial state and then evaluates new states until the predicate holds might suffice, but I am not so sure how that translates into the notion of termination of Turing machines. Or maybe I'm just generally way off.

-
I don't know the answer myself, but I see that the Wikipedia article on Rule 110 has a section titled "proof of universality". Have you looked at that? – MJD Aug 9 '12 at 2:01
I have, but it's a bit too complicated for me and seems to go deeper into the details of the proof than I need for my question. The sentence "The function of the universal machine in Rule 110 requires an infinite number of localized patterns to be embedded within an infinitely repeating background pattern." jumps out -- it just so happens that the language I was using, Haskell, supports infinite data structures, but they need to be (obviously) computable infinite data structures, and I'm not sure if that's what the proof uses. – Joshua Greg Aug 10 '12 at 0:15

For all classical cellular automata (CA), the transition function which computes the next state of a cell (given the current state of that cell and the states of all the cells in its neighbourhood) is primitive recursive (and usually, in fact, very simple.)

To evolve a CA form, one iteratively applies the transition function to all cells in the playfield. You couldn't technically consider this process primitive recursive, because it does not necessarily ever have to come to an end.

In fact, classical CA do not specify when their evolution should come to an end. This makes them a different kind of beast from classical Turing machines, which have a halt state. A CA cannot directly simulate a Turing machine unless you introduce a predicate that says that you consider the CA evolution to have halted. As an example, the predicate might be that all cells in the playfield have assumed a certain state.

So when someone says a CA is Turing-complete, they're being a little flexible with the notion. In terms of computability this is generally harmless, so long as the predicate is a primitive recursive function (again, like the transition function, it usually can in fact be very simple.)

I'm not entirely sure I fully understand your final question, but it sounds like you are asking how you would prove that some other system is Turing-complete by reducing it to the Rule 110 automaton. You could do that by showing that, for every instance of your system, there is a corresponding instance of the Rule 110 automaton which faithfully represents it, and that there is some predicate that is true for Rule 110 playfields when (and only when) your system has halted.

EDIT: Everything I've said above applies to CA's in general, and I just noticed the comment regarding the initial playfield of the Rule 110 automaton.

To show that some CA's are Turing-complete, the construction (beyond stipulating a halting predicate) also involves filling the CA's playfield with some pattern beyond the trivial pattern of "all cells are in one particular state". (I believe the proof that Wireworld is Turing-complete also uses this notion; the playfield is filled with a repeating pattern of gates.) This is generally not a problem, so long as that pattern is computable. The Turing machine simulating the CA can simply write the next state in that pattern to the part of the tape that it is using to represent that part of the CA's playfield, when it comes time for the Turing machine to simulate that part of the playfield for the first time.

If you want to show that some system is Turing-complete by reducing it to a CA which has been proved Turing-complete in this manner, you would have to keep in mind that the CA's initial playfield needs to be set up like this, but beyond that it would likely not be a major consideration in your reduction.

-