Can someone explain Rule 110 in the simplest way possible?

Question

I can't wrap my head around what the Wikipedia article or the answer here say. Can someone explain Rule 110 in simple terms? How does it guarantee Turing completeness?

Answer 1

My attempt at a succinct, layman's terms explanation:

• Rule 110 is an elementary cellular automaton: a rule for transforming a finite pattern of 1's and 0's into another pattern of 1's and 0's.
• When Rule 110 is iteratively applied on certain input bit sequences, patterns emerge depending on sub-sequences found in the input bits. Given enough iterations, the following can happen:
  • The original sub-sequence appears in the same location as in the original input.
  • The original sub-sequence is preserved but 'moves' to a different location in the bitfield.
  • Two sub-sequences moving toward each other interact and 'pass through' each other.
  • Two sub-sequences combine to create a new sub-sequence.
• Different sub-sequences can be given symbolic meaning like '1', '0', 'clock pulse', or 'production rule' that correspond to the elements of a cyclic tag system.
• With many iterations of Rule 110 on a carefully constructed input bitfield, the interaction of the sub-sequences simulates the behavior of a cyclic tag system.
• A cyclic tag system can be used to simulate a universal Turing machine. Thus a cyclic tag system is Turing-complete.
• Since Rule 110 can simulate a cyclic tag system, it too is Turing-complete.

Answer 2

I'll have a go at elaborating: I don't think you are looking for more details of the proof which is already quite complex in the article, although it clearly omits many details.

To quote from the article you cite: "In an elementary cellular automaton, a one-dimensional pattern of 0's and 1's evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 depends in the new generation on its current value, as well of that of its two neighbors. The Rule 110 automaton has the following set of rules..." (see the wikipedia table that follows)

The starting point, which you can view as the data, but which can be taken as a representation of code (representing code as data is necessary for any proof of Turing-completeness; this goes back to Turing's original results), is a sequence of 0's and 1's, often, but not necessarily, surrounded on both sides by cells containing just 0. Rule 110 shows how that sequence evolves. For instance, if there is a pattern of 3 1's in one row, the middle 1 will "die" (turn into a 0) in the next row. What happens to its two neighbours depends on how the pattern extends beyond them. The triangular diagrams you see are a graphical representation of the evolution of the automaton from the original state, coding 1 as black and 0 as white and representing evolution from above to below. The initial state is often very short in length to show how very complex patterns can evolve from simple initial states.

Two unusual features of the proof of Turing completeness are that, firstly, it looks highly unlikely that such a very simple rule could do everything your favourite programming language could do, and secondly, which makes the first fact rather less amazing, is that the proof requires an infinitely long repeating background on which to work its magic. I cannot see anything fundamentally dishonest about this though; no more so than assuming a potentially infinite or semi-infinite blank tape, as Turing originally did.

To understand the proof properly you would need to get to grips with how data (and later, code) is encoded in the starting pattern, and it also looks as if familiarity with cyclic tag systems would help enormously. I'm not the person to explain those.

Although it may seem harder to understand the situation with a 2-D cellular automaton, such as Conway's "Game of Life", I found it instructive to play with that game, studying "gliders", "glider guns" and "puffer trains" and other amusing constructions. (A puffer train constructs glider guns and a glider gun fires gliders). These can be used to establish Turing-completeness for this automaton as well.

You may also find the talk page informative (you are not alone in not grasping the point, see the entry beginning "the pictures don't make any sense to me..").