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

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..").

Answer 2

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 3

In 1970 John Conway has invented Game of Life.

Ever since, I think almost every programmer tried to write its implementation - I certainly did long time ago, and it was a lot of fun.

This game is actually cellular automaton, which sets simple rules between generations of cells in infinite 2-dimensional plane. For example, if in current generation cell has less than 2 neighbors alive (bit value 1), then it should die in next generation of loneliness. If it has more than 3 neighbors alive, it should die of overcrowding. If empty (bit value 0, or dead) cell has exactly 3 neighbors, it will cause it to be born (become 1).

Since then, it was found that Game of Life is surprisingly complex - it can generate a lot of very complex patterns that continue to evolve. Also, it was shown that it is Turing-complete, that is, you can encode arbitrarily complex algorithms using starting cell combination as a program, and final combination as a result. However, it took few years to find how to actually generate complicated forms, like gliders or guns.

Now back to what rule 110 is. Simply put, rule 110 is one-dimensional variation of Game of Life.

110 is just a decimal number representation of binary string 01101110 which is short form of rule system of how current generation of cells (bits) will be translated into next one, similar to Game of Life's rule system of cells dying of loneliness or overcrowding and being born of having exactly three neighbors.

Much like Game of Life, it has been proven that rule 110 is Turing-complete. You can encode arbitrarily complex algorithm using starting cells (bits) combination as your program, and final bits combination as a result.

Answer 4

An implementation in python:

(Be adviced: actual python programmers would kill you for this)

import time

seed = raw_input("Feed me a string! (At least 3 characters long please)\n>")

lastline = '>'
iterator = 0

while (iterator<len(seed)):
    temp = (ord(seed[iterator]))%2
    if (temp == 1):
        lastline += '#'
    else:
        lastline += ' '
    iterator += 1

stop = 0
while (stop != 1): #Keep printing as long as CTRL-C isn't pressed
    #dummy = raw_input(lastline)
    print lastline
    iterator = 0
    nextline = '>'


    while (iterator<len(seed)):    #Convert entire string

        if (len(seed) < 3): # if wrong
            print "You had ONE JOB!"
            stop = 1

        elif (iterator == 0): # if at start
            if (lastline[1] == ' '):
                nextline += ' '
            else:
                nextline += '#'

        elif (iterator+1 == len(seed)): # if at end
            if (lastline[iterator+1] == ' '):
                nextline += ' '
            else:
                nextline += '#'

        else: #if in middle
            if (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #111
                nextline += ' '
            elif (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #110
                nextline += '#'
            elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #101
                nextline += '#'
            elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == ' '): #100
                nextline += ' '
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #011
                nextline += '#'
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #010
                nextline += '#'
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #001
                nextline += '#'
            else: # (lastline[iterator-1] == ' ' and lastline[iterator] == ' ' and lastline[iterator+1] == ' '): #000
                nextline += ' '

        iterator += 1

    lastline = nextline
    time.sleep(0.02)