This is a simple note on Turing completeness of 2-neighbourhood 1-dimensional Cellular Automata.

A Cellular Automaton (pl. Cellular Automata) is a model of computation based on a* grid* of *cells* that *evolve* according to a simple set of rules. The grid can be multi-dimensional, the most famous and studied cellular automata are 1-dimensional and 2-dimensional. Each cell can be in a particular *finite state* ($k$-states CA), at each step of the evolution (*generation*) the cell changes its state according to its current state and the state of its *neighboring *cells. The number of neighbours considered is finite; for a 1-dimensional CA, the usual choice is the adjacent neighbours. A *m-neighbourhood* 1-dimensional CA is a CA in which the next state of cell $c_i$ depends on the state of $c_i$ and the state of the $m-1$ adjacent cells; usually $c_i$ is the central cell.

Formally, if $t_n(c_i)$ is the state of cell $c_i$ at time $t_n$:

$$t_{n+1}(c_i) = f( t_n(c_{i-\ell}), …, t_n(c_{i-2}), t_n(c_{i-1}), t_n(c_i), t_n(c_{i+1}), t_n(c_{i+2}), …, t_n(c_{i+\ell}) )$$

and $m = 2\ell+1$.

For more details and basic references see: Das D. (2012) A Survey on Cellular Automata and Its Applications.

Even basic cellular automata can be Turing Complete, for example see the (controversial) proof of Turing completeness of the 3-neighbourhood Cellular Autaton identified by Rule 110 .

If only 1 neigbour is considered (i.e. the next state of a cell only depend on its current state), then we cannot achieve Turing completeness. But with 2-neighbourhood and enough states it’s possible to emulate every CA.

Continue reading