rule110.md

   1 # Rule 110
   2
   3 *Not to be [confused](often_confused.md) with [rule 34](rule43.md) xD*
   4
   5 Rule 110 is a specific [cellular automaton](cellular_automaton.md) (similar to e.g. [Game of Life](game_of_life.md)) which shows a very interesting behavior -- it is one of the simplest [Turing complete](turing_completeness.md) (computationally most powerful) systems with a balance of stable and [chaotic](chaos.md) behavior. In other words it is a system in which a very complex and interesting properties emerge from extremely simple rules. The name *rule 110* comes from [truth table](truth_table.md) that defines the automaton's behavior. Its **extreme simplicity** combined with full computational power is what makes rule 110 of great interest -- for example it can relatively easily be implemented as a [mechanical computer](mechanical.md) using only marbles and a very simple maze (there's a video somewhere on the Internet).
   6
   7 Rule 110 is one of 256 so called elementary [cellular automata](cellular_automaton.md) which are special kinds of cellular automata that are one dimensional (unlike the mentioned [Game Of Life](game_of_life.md) which is two dimensional), in which cells have 1 bit state (1 or 0) and each cell's next state is determined by its current state and the state of its two immediate neighboring cells (left and right). Most of the 256 possible elementary cellular automata are "boring" but rule 110 is special and interesting. Probably the most interesting thing is that rule 110 is [Turing complete](turing_completeness.md), i.e. it can in theory compute anything any other computer can, while basically having just 8 rules. 110 (along with its equivalents) is the only elementary automaton for which Turing completeness has been [proven](proof.md).
   8
   9 For rule 110 the following is a table determining the next value of a cell given its current value (center) and the values of its left and right neighbor.
  10
  11 |left|center|right|center next|
  12 |----|------|-----|-----------|
  13 | 0  | 0    | 0   | 0         |
  14 | 0  | 0    | 1   | 1         |
  15 | 0  | 1    | 0   | 1         |
  16 | 0  | 1    | 1   | 0         |
  17 | 1  | 0    | 0   | 1         |
  18 | 1  | 0    | 1   | 1         |
  19 | 1  | 1    | 0   | 1         |
  20 | 1  | 1    | 1   | 0         |
  21
  22 The rightmost column is where elementary cellular automata differ from each other -- here reading the column from top to bottom we get the [binary](binary.md) number 01101110 which is 110 in [decimal](decimal.md), hence we call the automaton rule 110. Some automata behave as "flipped" versions of rule 110, e.g. rule 137 (bit inversion of rule 110) and rule 124 (horizontal reflection of rule 110) -- these are in terms of properties equivalent to rule 110.
  23
  24 The following is an output of 32 steps of rule 110 from an initial tape with one cell set to 1. Horizontal dimension represents the tape, vertical dimension represents steps/time (from top to bottom).
  25
  26 ```
  27 #
  28 ##
  29 ###
  30 # ##
  31 #####
  32 #   ##
  33 ##  ###
  34 ### # ##
  35 # #######
  36 ###     ##
  37 # ##    ###
  38 #####   # ##
  39 #   ##  #####
  40 ##  ### #   ##
  41 ### # ####  ###
  42 # #####  ## # ##
  43 ###   ## ########
  44 # ##  ####      ##
  45 ##### #  ##     ###
  46 #   #### ###    # ##
  47 ##  #  ### ##   #####
  48 ### ## # #####  #   ##
  49 # ########   ## ##  ###
  50 ###      ##  ###### # ##
  51 # ##     ### #    #######
  52 #####    # ####   #     ##
  53 #   ##   ###  ##  ##    ###
  54 ##  ###  # ## ### ###   # ##
  55 ### # ## ###### ### ##  #####
  56 # ########    ### ##### #   ##
  57 ###      ##   # ###   ####  ###
  58 # ##     ###  ### ##  #  ## # ##
  59 ```
  60
  61 The output was generated by the following [C](c.md) code.
  62
  63 ```
  64 #include <stdio.h>
  65
  66 #define RULE 110 // 01100111 in binary
  67 #define TAPE_SIZE 64
  68 #define STEPS 32
  69
  70 unsigned char tape[TAPE_SIZE];
  71
  72 int main(void)
  73 {
  74   // init the tape:
  75   for (int i = 0; i < TAPE_SIZE; ++i)
  76     tape[i] = i == 0;
  77
  78   // simulate:
  79   for (int i = 0; i < STEPS; ++i)
  80   {
  81     for (int j = 0; j < TAPE_SIZE; ++j)
  82       putchar(tape[j] ? '#' : ' ');
  83
  84     putchar('\n');
  85
  86     unsigned char state = // three cell state
  87       (tape[1] << 2) |
  88       (tape[0] << 1) |
  89       tape[TAPE_SIZE - 1];
  90
  91     for (int j = 0; j < TAPE_SIZE; ++j)
  92     {
  93       tape[j] = (RULE >> state) & 0x01;
  94       state = (tape[(j + 2) % TAPE_SIZE] << 2) | (state >> 1);
  95     }
  96   }
  97
  98   return 0;
  99 }
 100 ```
 101
 102 Discovery of rule 110 is attributed to [Stephen Wolfram](wolfram.md) who introduced elementary cellular automata in 1983 and conjectured Turing completeness of rule 110 in 1986 which was proven by Matthew Cook in 2004.
 103
 104 ## See Also
 105
 106 - [Game Of Life](game_of_life.md)
 107 - [Langton's Ant](langtons_ant.md)
 108 - [interaction net](interaction_net.md)