Rule 110

Example

Rule 110 is the one-dimensional cellular automaton with states $\set{0, 1}$, neighbourhood $\set{-1, 0, 1}$ and the following local rule $f$.

The bottom row, read as a binary numeral, is $01101110_2 = 64 + 32 + 8 + 4 + 2 = 110$, which gives the name under Wolfram's numbering. The global map is $F(x)_i = f(x_{i-1}, x_i, x_{i+1})$ for all $i \in \Z$. It is a cellular automaton because the new value at each site depends only on the sites at offsets $-1, 0, 1$. The same rule $f$ is used at every site.

Check on a small configuration: let $x$ have a single $1$ at site $0$ and $0$ elsewhere. At site $-1$ the neighbourhood is $001$, so the new value is $1$. At site $0$ it is $010$, so the new value is $1$. At site $1$ it is $100$, so the new value is $0$. All other sites see $000$ and stay $0$. So $F(x)$ has $1$ at sites $-1$ and $0$, and the pattern grows to the left.