Elementary cellular automaton

These rules will exhibit the same behavior up to reflection through a vertical axis, and so are equivalent in a computational sense.

It turns out that reflection and complementation are automorphisms of the monoid of one-dimensional cellular automata, as they both preserve composition.

[2] One method used to study these automata is to follow its history with an initial state of all 0s except for a single cell with a 1.

This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in base 4.

Rule 110 has the perhaps surprising property that it is Turing complete, and thus capable of universal computation.

This can be obtained by taking the coefficients of the successive powers of (1+x+x2) modulo 2 and interpreting them as integers in binary.

A second way to investigate the behavior of these automata is to examine its history starting with a random state.

In the following gallery, this evolution from random initial conditions is shown for each of the 88 inequivalent rules.

[7] Rule 73 is Class 2[8] because any time there are two consecutive 1s surrounded by 0s, this feature is preserved in succeeding generations.

This effectively creates walls which block the flow of information between different parts of the array.

These walls will form with probability 1 for completely random initial conditions.

However, if the condition is added that the lengths of runs of consecutive 0s or 1s must always be odd, then the automaton displays Class 3 behavior since the walls can never form.

Many interacting structures have been cataloged which collectively are expected to be sufficient for universality.