Wolfram's classification
A cellular automaton, according to Stephen Wolfram's 1983 classification scheme, belongs to any of the four classes judging from its behaviour.
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 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, there has been very little interest in detailed investigation of class one automata, and none appear to have established names.[citation needed]
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 lives 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 absense 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 | ? |
| 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/45678 | 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.
See also
Reference
- Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002. pp 231-249.