The rule is number 126.

Non-deterministic Turing machines Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by NTMEvolve[rule_, inits_, t_Integer] := Nest[ Union[Flatten[Map[NTMStep[rule, #]&, #], 1]]&, inits, t] NTMStep[rule_List, {s_, a_, n_}] /; 1 ≤ n ≤ Length[a] := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule], {1}]

The definition of the function f for rule 90 that we gave above is essentially just a look-up table. But it is also possible to define this function in an algebraic way f[p_, q_, r_] := Mod[p + r, 2] Algebraic definitions can also be given for other rules: • Rule 254 (page 24 ): 1 - (1 - p)(1 - q)(1 - r) • Rule 250 (page 25 ): p + r - p r • Rule 30 (page 27 ): Mod[p + q + r + q r, 2] • Rule 110 (page 32 ): Mod[(1 + p) q r + q + r, 2] In these definitions, we represent the values of cells by the numbers 1 or 0. … And in this case cellular automaton rules become logic expressions: • Rule 254: Or[p, q, r] • Rule 250: Or[p, r] • Rule 90: Xor[p, r] • Rule 30: Xor[p, Or[q, r]] • Rule 110: Xor[Or[p, q], And[p, q, r]] (Note that Not[p] corresponds to 1 - p , And[p, q] to p q , Xor[p, q] to Mod[p + q, 2] and Or[p, q] to Mod[p q + p + q, 2] .)

Despite the simplicity of the rule on the facing page that generates the primes, the actual sequence of primes that is obtained seems in many respects remarkably random.

The underlying rules for systems like cellular automata are however usually rather different from those for systems based on numbers. The main point is that the rules for cellular automata are always local: the new color of any particular cell depends only on the previous color of that cell and its immediate neighbors. … And in fact most simple arithmetic operations have the property The results of following the same rule as on the previous page , starting from the value 6.

The question of what size of perturbations can be tolerated without significant effect depends on the details of the underlying rules. And as the pictures suggest, rules which yield more complex behavior tend to be able to tolerate only smaller sizes of perturbations. … The effect of changing the number of initial black cells in the rule 30 cellular automaton shown above.

An example is rule 110, in which repetitive domains form with period 14 in space and 7 in time, but as the second picture below illustrates, the localized structures which separate these domains take a very long time to disappear. … A cellular automaton (rule 184) in which domains quickly combine to make the whole system repetitive in space. The behavior of rule 110 starting from random initial conditions.

It turns out that as illustrated in the picture below rule 30 has a property somewhat like the additive cellular automaton discussed two pages ago : in addition to allowing one row to be deduced from the row above, it allows columns to be deduced from columns to their right. … Sideways evolution in rule 30. … The possibility of (b) is a consequence of one-sided additivity in rule 30; it leads to some level of cryptanalysis if the encrypting sequence consists of a complete column of cells.

In case (a) the rules for the mobile automaton are set up to emulate the rule 90 elementary cellular automaton; in case (b) they are set up to emulate rule 30.

For as we discussed on page 83 , neighbor-independent substitution systems can generate only patterns that are either repetitive or nested—so they can never yield the more complicated patterns that are, for example, needed to emulate rule 30. … Neighbor-dependent substitution systems that emulate cellular automata with rules 90 and 30. The systems shown are simple examples of neighbor-dependent substitution systems with highly uniform rules always yielding just one cell and corresponding quite directly to cellular automata.