Wolfram's Classification of Cellular Automata

In his influential paper "University and Complexity in Cellular Automata" [Physica D 10 (1984) 1-35; all page numbers refer to the reprint in Cellular Automata and Complexity, Addison-Wesley 1994, pp. 115-157], Stephen Wolfram proposed a classification of cellular automaton rules into four types, according to the results of evolving the system from a "disordered" initial state:

  1. Evolution leads to a homogeneous state.
  2. Evolution leads to a set of separated simple stable or periodic structures.
  3. Evolution leads to a chaotic pattern.
  4. Evolution leads to complex localized structures, sometimes long-lived.

This classification was initially only for one-dimensional cellular automata, but in "Two-Dimensional Cellular Automata" [with N. H. Packard, J. Stat. Phys. 38 (1985) 901-946, reprinted in Cellular Automata and Complexity pp. 211-249] he extended it to two-dimensional automata.

Intuitively, according to this classification, one should only expect gliders, Turing-universality, and similar complex behavior in class 4 automata. Indeed, after discussing the existence of glider-like structures in a class 4 automaton, and their resemblance to structures in Conway's Life, Wolfram writes [p.151] "These analogies lead to the speculation that class 4 automata are characterized by the capability for universal computation."

However, there is a major flaw in this reasoning: because the classification is based on evolution from an unordered state, there is little reason for it to characterize behavior on initially ordered states. Our investigation has turned up gliders in systems that would likely be classified in each of the four classes: e.g. (in standard semitotalistic rule notation) B367/S3678 (class 1), B3/S256 or B3/S234 (both class 2 although having very different behavior), B345678/S12468 (class 3), and B3/S23 (class 4). This result throws the usefulness of this classification system into question.

The existence of a glider should automatically place a system into class 4, since such a complex localized structure would also arise from sufficiently large disordered initial conditions, however "sufficiently large" may be so huge that one can not in practice discover such structures by chance. Wolfram's classification may then be worse than useless: it may be ill-defined, since there is no quick test for distinguishing class 4 rules from other rules.

In "Two-Dimensional Cellular Automata", Wolfram mentions a number of particular rules. How do they stack up in terms of his classification and the existence of gliders?

Rule Ref. Classification   Gliders?
B236/S0468 Figs. 7(a), 13(g)   Class 3 No
B257/S27 Fig. 7(b) Yes
B13456/S01356 Fig. 7(d) No
B1/S012345678 Fig. 7(e) No
B137/S45678 Fig. 7(f) No
B34/S03456 Fig. 7(g) Unknown
B0578/S12456 Fig. 7(h) No
B0578/S045 Fig. 7(i) No
B378/S012345678   Fig. 9(a) No
B3/S234 Figs. 9(b), 13(b) Class 2 Yes
B367/S2346 Fig. 9(c) Yes
B018/S018 Fig. 13(c) Class 2 No
B123567/S0238 Fig. 13(f) Class 3 No
B135/S135 Fig. 13(h) Class 3 No
B3/S23 Fig. 13(i) Class 4 Yes

(When I could find a classification in Wolfram's paper, I listed it above; otherwise the "Classification" column is blank.)

A simpler classification scheme explains the data better than Wolfram's:

Cellular automata , D. Eppstein