Elementary cellular automaton

The sequence generated is 1, 3, 5, 11, 21, 43, 85, 171, ... (sequence A001045 in the OEIS). This is the sequence of Jacobsthal numbers and has generating function

${\displaystyle {\frac {1+2x}{(1+x)(1-2x)}}}$.

It has the closed form expression

${\displaystyle a(t)={\frac {4\cdot 2^{t}-(-1)^{t}}{3}}}$

Rule 156 generates the same sequence.

The sequence generated is 1, 5, 21, 85, 341, 1365, 5461, 21845, ... (sequence A002450 in the OEIS). This has generating function

${\displaystyle {\frac {1}{(1-x)(1-4x)}}}$.

It has the closed form expression

${\displaystyle a(t)={\frac {4\cdot 4^{t}-1}{3}}}$.

Note that rules 58, 114, 122, 178, 186, 242 and 250 generate the same sequence.

The sequence generated is 1, 7, 17, 119, 273, 1911, 4369, 30583, ... (sequence A118108 in the OEIS). This has generating function

${\displaystyle {\frac {1+7x}{(1-x^{2})(1-16x^{2})}}}$.

It has the closed form expression

${\displaystyle a(t)={\frac {22\cdot 4^{t}-6(-4)^{t}-4+3(-1)^{t}}{15}}}$.

The sequence generated is 1, 3, 5, 15, 17, 51, 85, 255, ...(sequence A001317 in the OEIS). This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in binary, which can be graphically represented by a Sierpinski triangle.

The sequence generated is 1, 5, 17, 85, 257, 1285, 4369, 21845, ... (sequence A038183 in the OEIS). This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in base 4. Note that rules 18, 26, 82, 146, 154, 210 and 218 generate the same sequence.

The sequence generated is 1, 7, 27, 119, 427, 1879, 6827, 30039, ... (sequence A118101 in the OEIS). This can be expressed as

${\displaystyle a(t)={\begin{cases}1,&{\mbox{if }}t=0\\[5px]7,&{\mbox{if }}t=1\\[7px]{\dfrac {1+5\cdot 4^{n}}{3}},&{\mbox{if }}t{\mbox{ is even otherwise}}\\[7px]{\dfrac {10+11\cdot 4^{n}}{6}},&{\mbox{if }}t{\mbox{ is odd otherwise}}\end{cases}}}$.

This has generating function

${\displaystyle {\frac {(1+2x)(1+5x-16x^{4})}{(1-x^{2})(1-16x^{2})}}}$.

The sequence generated is 1, 6, 20, 120, 272, 1632, 5440, 32640, ... (sequence A117998 in the OEIS). This is simply the sequence generated by rule 60 (which is its mirror rule) multiplied by successive powers of 2.

The sequence generated is 1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, ... (sequence A117999 in the OEIS). Rule 110 has the perhaps surprising property that it is Turing complete, and thus capable of universal computation.[2]

The sequence generated is 1, 7, 21, 107, 273, 1911, 5189, 28123, ... (sequence A038184 in the OEIS). This can be obtained by taking the coefficients of the successive powers of (1+x+x²) modulo 2 and interpreting them as integers in binary.

The sequence generated is 1, 7, 29, 115, 477, 1843, 7645, 29491, ... (sequence A118171 in the OEIS). This has generating function

${\displaystyle {\frac {1+7x+12x^{2}-4x^{3}}{(1-x^{2})(1-16x^{2})}}}$.

The sequence generated is 1, 3, 5, 15, 29, 55, 93, 247, ... (sequence A118173 in the OEIS). This has generating function

${\displaystyle {\frac {1+3x+4x^{2}+12x^{3}+8x^{4}-8x^{5}}{(1-x^{2})(1-16x^{4})}}}$.

The sequence generated is 1, 7, 29, 119, 477, 1911, 7645, 30583, ... (sequence A037576 in the OEIS). This has generating function

${\displaystyle {\frac {1+3x}{(1-x^{2})(1-4x)}}}$.

The sequence generated is 1, 3, 7, 15, 31, 63, 127, 255, ... (sequence A000225 in the OEIS). This is the sequence of Mersenne numbers and has generating function

${\displaystyle {\frac {1}{(1-x)(1-2x)}}}$.

It has the closed form expression

${\displaystyle a(t)=2\cdot 2^{t}-1}$.

Note: rule 252 generates the same sequence.

The sequence generated is 1, 7, 31, 127, 511, 2047, 8191, 32767, ... (sequence A083420 in the OEIS). This is every other entry in the sequence of Mersenne numbers and has generating function

${\displaystyle {\frac {1+2x}{(1-x)(1-4x)}}}$.

It has the closed form expression

${\displaystyle a(t)=2\cdot 4^{t}-1}$.

Note that rule 254 generates the same sequence.

In some cases the behavior of a cellular automaton is not immediately obvious. For example, for Rule 62, interacting structures develop as in a Class 4. But in these interactions at least one of the structures is annihilated so the automaton eventually enters a repetitive state and the cellular automaton is Class 2.[6]

Rule 73 is Class 2[7] 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. There are a finite number of possible configurations in the section between two walls so the automaton must eventually start repeating inside each section, though the period may be very long if the section is wide enough. 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.

Rule 54 is Class 4[8] and also appears to be capable of universal computation, but has not been studied as thoroughly as Rule 110. Many interacting structures have been cataloged which collectively are expected to be sufficient for universality.[9]