Table 1: Rule Forms and Equivalences

Forms of rules and equivalences between rules.

The table lists all 256 possible rules for , one-dimensional cellular automata. Such cellular automata consist of a line of sites, each with value 0 or 1. At each time step, the value of a site at position is updated according to the rule

This table lists the possible choices of .

Each digit in the binary representation of the rule number gives the value of for a particular set of . The digit corresponding to the coefficient of in the rule number gives the value of , where . Thus the leftmost digit in the binary representation of the rule number gives , the next gives , and so on, down to .

The table also gives the decimal and hexadecimal representations of the rule numbers.

Each can be considered a Boolean function of three variables, say , and . The table gives the minimal disjunctive normal form representations for these Boolean functions. Boolean multiplication and addition are used (corresponding to AND and OR operations). Bar denotes complementation. In each case, the expression with the minimal number of components, using only these operations, is given.

The column labelled ``dep'' gives the dependence of on each of the , and . The symbol -- indicates no change in when the corresponding is changed. The symbol denotes linear dependence of on the corresponding : whenever changes, also changes. The symbol denotes arbitrary dependence of . Rules such as 90 in which only and -- dependence occurs, are called additive, and can be represented as linear functions modulo two.

For each rule, the table gives rules equivalent under simple transformations. ``conj'' denotes conjugation: interchange of \vadjust {}the roles of 0 and 1. ``refl'' denotes reflection. Rules invariant under reflection are symmetric. ``c.r.'' denotes the combined operation of conjugation and reflection.

Many of the properties considered in this Appendix are unaffected by these transformations. The rules form equivalence classes under these transformations, and it is usually convenient to consider only the minimal (lowest-numbered) representatives of each class, as given by the last column in the table.

In some cases, further equivalences between rules can be used. Table 7 gives one important set of such further equivalences.

Some special rules are:

Table by Lyman P. Hurd (Mathematics Department, Princeton University). (Boolean expressions by S. Wolfram.)

previous  l  next