|
Articles Cellular Automata Tables of Cellular Automaton Properties (1986)
Tables of Cellular Automaton Properties (1986) |
|
Cellular automaton rules with 
and 
can be expressed as Boolean functions of three variables, as in table 1. Iterations of these rules for 
steps correspond to functions of 
variables, which may be expressed as Boolean expressions.
The minimal Boolean expressions obtained after one step were given in table 1. This table gives the numbers of terms in Boolean expressions obtained after time steps. An increase in these numbers potentially reflects increasing difficulty of computing the outcome of more steps of cellular automaton evolution.
The first number in each case gives the number of prime implicants in the corresponding Boolean expression. The possible values of a set of 
Boolean variables correspond to the vertices of a Boolean -cube. The cases in which a Boolean function has value 1 then correspond to a region of the Boolean -cube. The number of prime implicants is essentially the number of hyperplanes of various dimensions which must be combined to form this region.
Boolean expressions can conveniently be stated in a disjunctive normal form (DNF), in which they are written as a disjunction (OR) of conjunctions (ANDs). The number of prime implicants gives an upper bound on the number of terms needed in such a form.
Notice that complementation of a function has no simple effect on its DNF expression. As a result, the table includes minimal representatives for all rules from table 1 not related by reflection.
The general problem of finding an absolutely minimal DNF representation for a function appears to be computationally intractable. The table gives in parentheses the numbers of terms in minimal DNF expressions found by the espresso computer program (R. Rudell, Computer Science Department, University of California, Berkeley, 1985) which incorporates known algebraic and heuristic techniques. In most cases, the results given are probably absolutely minimal.
