The rule for this cellular automaton is somewhat complicated—it involves a total of sixteen colors possible for each cell—but the example demonstrates the point that in principle a cellular automaton can compute the primes. … The rule for the cellular automaton shown here involves 16 possible colors for each cell.

But with a total of 218 out of the 65,536 possible rules, one gets somewhat different behavior, as cases (g) and (h) below show. … Examples of mobile automata with various rules.

The only pattern that is known to be obtainable by evolving down the page according to a simple local rule is (j), which corresponds to the rule 60 elementary cellular automaton.

Square root of rule 30 Although rule 30 cannot apparently be decomposed into other k = 2 , r = 1 cellular automata, it can be viewed as the square of the k = 3 , r = 1/2 cellular automata with rule numbers 11736, 11739 and 11742.

Spacetime symmetric rules With k = 2 and the neighborhoods shown here, only the additive rules 90R, 105R, 150R and 165R are space-time symmetric. For larger k and larger neighborhoods, there presumably begin to be non-additive rules with this property.

Code 10 Rule 30 is by many measures the simplest cellular automaton that generates randomness from a single black initial cell. But there are other simple examples—that historically I noticed slightly earlier than rule 30, though did not study—that occur in k = 2 , r = 2 totalistic rules. And indeed among the 64 such rules, 13 show randomness.

Cellular automaton [Nand] formulas For 1 step, the elementary cellular automaton rules are exactly the 256 n = 3 Boolean functions. … They require an average of about 11.6 Nand operations, and a maximum of 27 (achieved by rules 107 and 121). For rule 254 the result after t steps (which is always asymmetric, even though the rule is symmetric) is Nest[{{#, # 〚 2 〛 + 1}, # 〚 2 〛 + 1} &, {{1, 1}, {2, 2}}, t - 2] If explicit copy operations were allowed, then the number of Nand operations after t steps could not increase faster than t 2 for any rule.

More complicated rules [and reducibility] The standard rule for a cellular automaton specifies how every possible block of cells of a certain size should be updated at every step. … Note that dealing with blocks of different sizes requires going beyond an ordinary cellular automaton rule. But in a sequential substitution system—and especially in a multiway system (see page 776 )—this can be done just as part of an ordinary rule.

Other [symbolic systems] rules If only a single variable appears in the rule, then typically only nested behavior can be generated—though in an example like ℯ [x_][_]  ℯ [x[ ℯ [ ℯ ][ ℯ ]][ ℯ ]] it can be quite complex. The left-hand side of each rule can consist of any expression; ℯ [ ℯ [x_]][y_] and ℯ [ ℯ ][x_[y_]] are two possibilities. However, at least with small initial conditions it seems easier to achieve complex behavior with rules based on ℯ [x_][y_] .

Despite this, however, the overall spacetime pattern of cells is not arbitrary, but is instead determined by the underlying rules. … For arbitrary rules, difference patterns of the kind shown on page 250 can get both larger and smaller. In a reversible rule, such patterns can grow and shrink, but can never die out completely.