How is the rule 110 Turing complete?

Problem Detail: 

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

Asked By : Pureferret

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4779