Wolfram's classification

From LifeWiki
Jump to navigation Jump to search

A cellular automaton, according to Stephen Wolfram's 1983 classification scheme, belongs to any of the four classes judging from its behaviour.

Invented for the range-1 one-dimensional rules Wolfram originally investigated, it generalises poorly to other rulespaces. David Eppstein, among others, has criticized the usefulness of Wolfram's classification system when applied to Life-like 2D CA rules.

Class one cellular automata

Class one cellular automata are those where the development of all patterns tends towards vacuum.

Class one has many similarities to class two cellular automata. It is in several cases simple to prove that no infinite growth pattern can exist in a Life-like or closely related cellular automaton. Showing the nonexistence of still lifes or oscillators can be, however, more difficult. As such, it can be difficult to distinguish class two CA whose ash has extremely low density from class one.

It is debatable whether agar solutions are sufficient to claim a CA as class two and not class one. As an extreme example, in the Life-like CA B/S8, exactly one pattern exists that does not evolve to vacuum: "antivacuum", the infinite field of live cells.

Given their highly predictable nature, class one automata have received relatively little attention, and none have established names.

Class two cellular automata

Class two cellular automata are those where the development of all patterns tends toward simple stationary ash — either constellations of separate still lifes and oscillators, or larger regions of stable and oscillating cells.

A simple condition for considering a Life-like cellular automaton to be either class two or class one is the absence of birth conditions capable of extending the pattern's bounding box: B0, B1, B2 or B3. Beyond this, positively identifying a rule as class two is mostly not an exact science.

The Vote rule (B5678/S45678) is one of the better known provably class two cellular automata.

Class three cellular automata

Class three cellular automata are those where most patterns tend towards chaotic, seemingly infinite growth. They are thus the polar opposite of class one CA. The term explosive is frequently applied to these rules or patterns in them.

The definition of "most" is not exact. Several class three rules have only been identified as such in retrospect, having been previously considered class four cellular automata; since most small patterns may in fact stabilize. An early example is 34 Life. Arguably HighLife may be an example as well, as the small natural replicator means that sufficiently large patterns tend towards infinite growth.

A subdivision, not quite exact, could be made between class three rules that produce "active" chaos, and those that produce a stable mass of live cells (often with encased holes or oscillators).

Class three CA known in detail include:

Rulestring Name Character Still lifes Oscillators Spaceships Orderly infinite growth patterns
B2/S Seeds Active no yes yes yes
(guns, puffers, rakes)
B2/S0 Live Free or Die Active yes (dot) yes yes yes
(guns, puffers, rakes)
B3/S023 DotLife Active yes yes yes yes
B37/S23 DryLife Active yes yes yes yes
B34/S34 3-4 Life Active yes (block) yes yes yes
(wickstretcher)
B35678/S5678 Diamoeba Stable no yes yes yes
(wickstretchers, spacefillers)
B3/S012345678 Life without death Stable yes no no yes
(ladders)

Some others with established names:

Rulestring Name Character
B234/S Serviettes Active
B3/S1234 Mazectric Stable
B3/S12345 Maze Stable
B3/S45678 Coral Stable

Class four cellular automata

Class four cellular automata are those where most patterns tend towards a mixture of order and randomness. In microscopic scale (that is, not considering meta-pattern constructions like 0E0P metacell), Conway's Game of Life falls under this class, as do Pedestrian Life, Highlife, EightLife, and Sqrt replicator rule. Even so, there is a continuum of rules which have more or less relative activity compared to B3/S23, and even some very long-lived rules can be considered Class four and not Class three since they don't expand forever.

See also

References