Cellular Automata/Examples on Rule 110

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Formal definition[edit | edit source]

The commonly known 1D binary CA rule 110 is defined as where

  • can be finite or infinite
  • is a set of two values
  • is the neighborhood of size with symmetric radius
  • is the local transition function rule
000 -> 0
001 -> 1
010 -> 1
011 -> 1
100 -> 0
101 -> 1
110 -> 1
111 -> 0
  • is the optional boundary usually chosen not to interfere with the quiescent background of all zeros

De Bruijn diagrams[edit | edit source]

Overlap[edit | edit source]

Neighborhoods of adjacent cells overlapping

Neighborhoods of adjacent cells are overlapping for cells. There are different overlaps or written in compact form .

Symbolic De Bruijn diagram[edit | edit source]

Symbolic De Bruijn diagram for rule 110

The De Bruijn diagram has nodes (one for each of the possible overlaps) and links (one for each of the possible neighborhoods).

preimage matrix[edit | edit source]

There are two preimage matrices, one for each of the available cell states.

Boundary conditions[edit | edit source]

There are two commonly used backgrounds, the quiescent background and the ether.

Quiescent background[edit | edit source]

The quiescent background is an infinite sequence with period of length cell.

There are always exactly two preimages for this background independently on the length of the sequence from a single cell to infinity (see the preimage network). The left and right boundary vectors are equal.

Preimage network for rule 110 and the quiescent background configuration

Ether background[edit | edit source]

The ether background is an infinite sequence with period of length cells. This is the prevailing background emerging from a random initial configuration.

The number of preimages of the ether configuration increases exponentially with the sequence length going to infinity. A circular lattice is used to calculate the number of preimages of the period .

Because of the exponential growth the boundary vector does not represent the number of preimages of the whole infinite background but only weights derived from the period's preimages. The value of the boundary vector depends on the position inside the period, in the next table vectors are columns for each of the 14 positions.

 overlaps | boundary vectors
---------------------------------------------------------------------
 00       | 0   0   0   0   2   2   0   0   1   0   0   0   0   0
 01       | 0   0   0   0   0   0   2   0   0   1   1   0   2   0
 10       | 0   0   0   2   0   0   0   1   0   1   0   2   0   0
 11       | 2   2   2   0   0   0   0   1   1   0   1   0   0   2
---------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

Preimage network for rule 110 and the ether configuration

Listing preimages[edit | edit source]

Bounded lattice[edit | edit source]

An example how to list preimages of the ether sequence on an bounded lattice

 overlaps | backward preimage count vectors
----------------------------------------------------------------------
 00       | 0   0   0   0   7   7   7   0   4   4   3   2   2   1   1
 01       | 0   0   0   7   0   0   4   7   0   5   4   3   2   2   1
 10       | 0   0   0   0   7   7   7   0   4   4   3   2   2   1   1
 11       | 7   7   7   7   0   0   0   4   3   3   2   2   1   1   1
----------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1
 overlaps | forward preimage count vectors
----------------------------------------------------------------------
 00       | 1   2   2   2   0   1   1   0   0   1   0   0   0   0   0
 01       | 1   0   0   0   2   0   0   1   0   0   1   1   1   2   2
 10       | 1   0   0   0   1   0   0   0   1   0   1   1   2   2   3
 11       | 1   1   1   1   0   0   0   0   1   1   0   1   1   1   2
----------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

Weights for the preimage network

 overlaps | neighborhood (link) weights
----------------------------------------
 000      | 0 0 0 0 0 7 0 0 0 0 0 0 0 0
 001      | 0 0 0 0 0 0 7 0 0 4 0 0 0 0
 010      | 0 0 0 0 0 0 0 4 0 0 2 2 1 2
 011      | 0 0 0 0 0 0 0 3 0 0 2 1 1 2
 100      | 0 0 0 0 7 0 0 0 4 0 0 0 0 0
 101      | 0 0 0 0 0 0 0 0 0 0 3 2 4 2
 110      | 0 0 0 7 0 0 0 0 0 3 0 2 1 1
 111      | 7 7 7 0 0 0 0 0 3 0 0 0 0 0
----------------------------------------
 sequence | 0 0 0 1 0 0 1 1 0 1 1 1 1 1
 overlaps | boundary vectors
----------------------------------------------------------------------
 00       | 0   0   0   0   0   7   7   0   0   4   0   0   0   0   0
 01       | 0   0   0   0   0   0   0   7   0   0   4   3   2   4   2
 10       | 0   0   0   0   7   0   0   0   4   0   3   2   4   2   3
 11       | 7   7   7   7   0   0   0   0   3   3   0   2   1   1   2
----------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

Preimage network for rule 110 and the ether sequence on unrestricted boundaries

cyclic lattice[edit | edit source]

 overlaps | preimage count matrices
---------------------------------------------------------------------------------------
 00       | 0000 0000 0000 0000 0232 0232 0232 0000 0121 0121 0111 0110 0011 0100 1000
 01       | 0000 0000 0000 0232 0000 0000 0121 0232 0000 0221 0121 0111 0110 0011 0100
 10       | 0000 0000 0000 0000 0232 0232 0232 0000 0121 0121 0111 0110 0011 0100 0010
 11       | 0232 0232 0232 0232 0000 0000 0000 0121 0111 0111 0110 0011 0100 0010 0001
---------------------------------------------------------------------------------------
 sequence |     0    0    0    1    0    0    1    1    0    1    1    1    1    1
 overlaps | boundary vectors
---------------------------------------------------------------------
 00       | 0   0   0   0   2   2   0   0   1   0   0   0   0   0
 01       | 0   0   0   0   0   0   2   0   0   1   1   0   2   0
 10       | 0   0   0   2   0   0   0   1   0   1   0   2   0   0
 11       | 2   2   2   0   0   0   0   1   1   0   1   0   0   2
---------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

Preimage network for rule 110 and the ether configuration on cyclyc boundaries

Subset diagram transition table[edit | edit source]

from |  to the left        |  to the right
--------------------------------------------------
0000 |  <-0-0000 <-1-0000  |  0000-0-> 0000-1->
0001 |  <-0-0001 <-1-0100  |  0001-0-> 0010-1->
0010 |  <-0-0000 <-1-0101  |  1000-0-> 0100-1->
0011 |  <-0-0001 <-1-0201  |  1001-0-> 0110-1->
0100 |  <-0-0000 <-1-1010  |  0000-0-> 0011-1->
0101 |  <-0-0001 <-1-1110  |  0001-0-> 0021-1->
0110 |  <-0-0000 <-1-1111  |  1000-0-> 0111-1->
0111 |  <-0-0001 <-1-1211  |  1001-0-> 0121-1->
1000 |  <-0-1010 <-1-0000  |  1000-0-> 0100-1->
1001 |  <-0-1011 <-1-0100  |  1001-0-> 0110-1->
1010 |  <-0-1010 <-1-0101  |  2000-0-> 0200-1->
1011 |  <-0-1011 <-1-0201  |  2001-0-> 0210-1->
1100 |  <-0-1010 <-1-1010  |  1000-0-> 0111-1->
1101 |  <-0-1011 <-1-1110  |  1001-0-> 0121-1->
1110 |  <-0-1010 <-1-1111  |  2000-0-> 0211-1->
1111 |  <-0-1011 <-1-1211  |  2001-0-> 0221-1->

Garden of Eden sequences[edit | edit source]

regular expression (the expression is left right symmetric)
0*1(00*1+1(1+00)*010)*1(1+00)*011(0+1)*[citation needed]
the shortest GoE sequence
01010[1]

Gliders[edit | edit source]

the ether
(00010011011111)*

See also[edit | edit source]

  1. Rule 110 at MathWorld
  2. Rule 110 at Wolfram Atlas
  3. Harold V. Mcintosh, Rule 110 as it rules relates to the presence of gliders
  4. Rule 110 at Wikipedia

Reference notes[edit | edit source]

  1. Wolfram, Stephen (May 14, 2002). A New Kind of Science. online. Champaign, IL: Wolfram Media, Inc. p. 1168. ISBN 1-57955-008-8. OCLC 47831356. {{cite book}}: External link in |others= (help)