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. When the rule number is even (so that an input of 000 does not compute to a 1) it makes sense to interpret state at each time,
t, as an integer expressed in binary, producing a sequence
a(
t) of integers. In many cases these sequences have simple, closed form expressions or have a
generating function with a simple form. The following rules are notable:
Rule 28 The sequence generated is 1, 3, 5, 11, 21, 43, 85, 171, ... . This is the sequence of
Jacobsthal numbers and has generating function :\frac{1+2x}{(1+x)(1-2x)}. It has the closed form expression :a(t) = \frac{4\cdot 2^t-(-1)^t}{3} Rule 156 generates the same sequence.
Rule 50 The sequence generated is 1, 5, 21, 85, 341, 1365, 5461, 21845, ... . This has generating function :\frac{1}{(1-x)(1-4x)}. It has the closed form expression :a(t) = \frac{4\cdot 4^t-1}{3}. Note that rules 58, 114, 122, 178, 186, 242 and 250 generate the same sequence.
Rule 54 The sequence generated is 1, 7, 17, 119, 273, 1911, 4369, 30583, ... . This has generating function :\frac{1+7x}{(1-x^2)(1-16x^2)}. It has the closed form expression :a(t) = \frac{22\cdot 4^t-6(-4)^t-4+3(-1)^t}{15}.
Rule 60 The sequence generated is 1, 3, 5, 15, 17, 51, 85, 255, .... 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.
Rule 90 The sequence generated is 1, 5, 17, 85, 257, 1285, 4369, 21845, ... . 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.
Rule 94 The sequence generated is 1, 7, 27, 119, 427, 1879, 6827, 30039, ... . This can be expressed as :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 :\frac{(1+2x)(1+5x-16x^4)}{(1-x^2)(1-16x^2)}.
Rule 102 The sequence generated is 1, 6, 20, 120, 272, 1632, 5440, 32640, ... . This is simply the sequence generated by rule 60 (which is its mirror rule) multiplied by successive powers of 2.
Rule 110 The sequence generated is 1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, ... . Rule 110 has the perhaps surprising property that it is
Turing complete, and thus capable of
universal computation.
Rule 150 The sequence generated is 1, 7, 21, 107, 273, 1911, 5189, 28123, ... . 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.
Rule 158 The sequence generated is 1, 7, 29, 115, 477, 1843, 7645, 29491, ... . This has generating function :\frac{1+7x+12x^2-4x^3}{(1-x^2)(1-16x^2)}.
Rule 188 The sequence generated is 1, 3, 5, 15, 29, 55, 93, 247, ... . This has generating function :\frac{1+3x+4x^2+12x^3+8x^4-8x^5}{(1-x^2)(1-16x^4)}.
Rule 190 The sequence generated is 1, 7, 29, 119, 477, 1911, 7645, 30583, ... . This has generating function :\frac{1+3x}{(1-x^2)(1-4x)}.
Rule 220 The sequence generated is 1, 3, 7, 15, 31, 63, 127, 255, ... . This is the sequence of
Mersenne numbers and has generating function :\frac{1}{(1-x)(1-2x)}. It has the closed form expression :a(t) = 2\cdot 2^t-1. Note: rule 252 generates the same sequence.
Rule 222 The sequence generated is 1, 7, 31, 127, 511, 2047, 8191, 32767, ... . This is every other entry in the sequence of
Mersenne numbers and has generating function :\frac{1+2x}{(1-x)(1-4x)}. It has the closed form expression :a(t) = 2\cdot 4^t-1. Note that rule 254 generates the same sequence. ==Images for rules 0-99==