# Cellular Automata/Examples on Rule 110

## Formal definitionEdit

The commonly known 1D binary CA rule 110 is defined as $\langle Z, S, N, f, B \rangle$ where

• $Z$ can be finite or infinite
• $S=\{ 0,1 \}$ is a set of two values
• $N=\{ -1,0,1 \}$ is the neighborhood of size $k=3$ with symmetric radius $k_0=1$
• $f$ is the local transition function rule $r=110$
000 -> 0
001 -> 1
010 -> 1
011 -> 1
100 -> 0
101 -> 1
110 -> 1
111 -> 0

• $B=\{ b_{-1},b_{1} \}$ is the optional boundary usually $B=\{ 0,0 \}$ chosen not to interfere with the quiescent background of all zeros

## De Bruijn diagramsEdit

### OverlapEdit

Neighborhoods of adjacent cells are overlapping for $k-1=2$ cells. There are $|S|^{k-1}=4$ different overlaps ${00,01,10,11}$ or written in compact form ${0,1,2,3}$.

### Symbolic De Bruijn diagramEdit

Symbolic De Bruijn diagram for rule 110

The De Bruijn diagram has $|S|^{k-1}=4$ nodes (one for each of the possible overlaps) and $|S|^k=8$ links (one for each of the possible neighborhoods).

$D= \begin{bmatrix} 0 & 1 & \cdot & \cdot \\ \cdot & \cdot & 1 & 1 \\ 0 & 1 & \cdot & \cdot \\ \cdot & \cdot & 1 & 0 \end{bmatrix}$

### preimage matrixEdit

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

$D(0)= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \qquad D(1)= \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$

### Boundary conditionsEdit

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

#### Quiescent backgroundEdit

The quiescent background is an infinite sequence with period $\alpha=\overline{0}$ of length $|\alpha|=1$ 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.

$b_L = b_R = [1,0,0,1]$

#### Ether backgroundEdit

The ether background is an infinite sequence with period $\alpha=\overline{00010011011111}$ of length $|\alpha|=14$ 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 $l$ going to infinity. A circular lattice is used to calculate the number of preimages of the period $\alpha$.

$p = p_c(\alpha)^{l/|\alpha|} = 2^{l/14}$

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


## Listing preimagesEdit

### Bounded latticeEdit

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

$b_L=b_R=b_u$
 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


Weigths for the preimage network

 overlaps | neighborhood (link) weigths
----------------------------------------
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


### cyclic latticeEdit

 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


### Subset diagram transition tableEdit

from |  to he 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 sequencesEdit

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

## GlidersEdit

the ether
(00010011011111)*