TOPICS
Search

Additive Cellular Automaton


An additive cellular automaton is a cellular automaton whose rule is compatible with an addition of states. Typically, this addition is derived from modular arithmetic. Additive rules allow the evolution for different initial conditions to be computed independently, then the results combined by simply adding. The results for arbitrary starting conditions can therefore be computed very efficiently by convolving the evolution of a single cell with an appropriate convolution kernel (which, in the case of two-color automata, would correspond to the set of initially "active" cells).

ElementaryCARule90Panel

A simple example of an additive cellular automaton is provided by the rule 90 elementary cellular automaton. As can be seen from the graphical representation of this rule, the rule as a function of left, central, and right neighbors is simply given by the sum of the rules for the left and right neighbors taken modulo 2, where white cells are assigned the value 0 and black cells are assigned 1. (This is equivalent to the XOR operation and means that "adding" two white cells or two black cells gives a white cell, while adding one white and one black cells gives a black cell.) For example, the rule for (1, 1, 1) is 1+1=0 (mod 2), the rule for (1, 1, 0) is 1+0=1 (mod 2), the rule for (1, 0, 1) is 1+1=0 (mod 2), and so on. Repeating this for each of the 2^3=8 possible states of neighbors gives

 01011010,
(1)

which is exactly the binary string defining the behavior of rule 90 (this rule is assigned the number 90 is because 90=01011010_2 in binary).

Rule 90 added to itself

The evolution of shifted versions of rule 90 are illustrated in the above figure. The figure on the left shows 31 iterations of rule 90 for an initial condition consisting of a single black square. Moving to the right, each figure shows the results of adding an additional black cell with displacement Deltax to the starting condition, increasing one generation per frame.

Additive cellular automata shifts

The illustration above shows the additivity more explicitly. In this animation, each frame corresponds to an initial conditions with the right cell shifted one unit further to the right. As can be seen, the portion of the pattern that does not overlap remains unchanged, while the overlapping portion is additive under the XOR operation.

Additive cellular automata

In general, a cellular automaton with k colors is additive if its rules can be written as a sum of integer multiples of its neighbors (mod k), where the integers can range from 0 to k. There are therefore k^(2r+1) additive rules among the k^(k^(2r+1)) possible rules with k colors and range r (Wolfram 2002, p. 952). The table below summarize the eight additive rules for the elementary cellular automata (k=2 and r=1 gives 2^(2·1+1)=2^3=8). In the table, c_i denotes the neighbor located at position i relative to the center.

ruleaddition (mod 2)
00
rule 60c_(-1)+c_0
rule 90c_(-1)+c_1
rule 102c_0+c_1
rule 150c_(-1)+c_0+c_1
170c_1
204c_0
240c_(-1)

For additivity of the above automata, the properties required were associativity and commutativity. It is possible to generalize the notion of additivity to other types of addition. In general, let phi(u) denote the cellular automaton evolution history of u, and let  direct sum denote a binary operator acting on the values of cells and, by extension, to their states and evolution. Then phi is an additive cellular automaton with respect to  direct sum if

 phi(u direct sum v)=phi(u) direct sum phi(v).
(2)

Some cellular automata have no interesting  direct sum , but others do, and these additions can be used to speed up calculations.

ElementaryCARule250Panel

Rule 250 provides another example of an additive elementary cellular automaton under the operation OR(c_(-1),c_1). By examining the set of rules, it can be verified that in each case, the resultant state is black if either (or both) neighbors is black, and white only if both neighbors are white. This corresponds to the set of rules

 11111010,
(3)

which is identical to the definition of rule 250.

Rule 250 added to itself
Additive cellular automata shifts

Generation-by-generation differences for the first few shifts and the entire pattern as a function of shift are illustrated above.

As a result of additivity, the evolutions of additive cellular automata behave similarly to the solutions of linear partial differential equations. In particular, they admit analogs of Green's functions such that, given an initial condition, the resulting evolution can be found by convolving the evolution of a single cell (which can be viewed as the analog of an integral kernel) with the initial condition (Wolfram 2002, p. 952).


See also

Cellular Automaton, Elementary Cellular Automaton, Commutative Monoid, Finite Field, Modular Arithmetic, Pascal's Triangle, Rule 60, Rule 90, Rule 102, Rule 150, Rule 250

Portions of this entry contributed by Todd Rowland

Explore with Wolfram|Alpha

References

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 264, 870, and 952-953, 2002.

Referenced on Wolfram|Alpha

Additive Cellular Automaton

Cite this as:

Rowland, Todd and Weisstein, Eric W. "Additive Cellular Automaton." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AdditiveCellularAutomaton.html

Subject classifications