Glossary of Terms
The vocabulary of cellular automata research has accumulated over seventy years across several disciplines, and the same concept sometimes has different names in different communities. This glossary collects the terms used throughout this hub and defines them with enough precision to be useful and enough context to be meaningful. Terms are listed alphabetically; most include links to pages where they are discussed in depth.
Alive / Dead The two states of a cell in Conway’s Life and related two-state CA. A cell is alive (often shown as a filled square or a specific color) or dead (empty). The entire dynamics of the system consists of cells switching between these states according to the rule. See also: The Bestiary.
B/S Notation The standard notation for specifying two-state life-like CA rules: B[birth-counts]/S[survival-counts]. Conway’s Life is B3/S23 — a dead cell is Born with 3 live neighbors; a live cell Survives with 2 or 3. The notation covers 2^18 = 262,144 possible rules. See: Beyond Conway: The Universe of Life-Like Rules.
Birth Rule The part of a B/S rule specifying when a dead cell becomes alive: the set of neighbor counts that trigger birth. In Life, this is B3 (exactly 3 live neighbors). See: [Glossary: B/S Notation].
Boundary Condition The rule applied at the edges of a finite simulation grid: what do cells at the edge “see” as their neighbors? Options include toroidal (edges wrap), fixed (edge neighbors are always dead), and reflected. See: Flat, Wrapped, and Beyond: Grid Topologies.
Cellular Automaton (CA) A computational model consisting of a grid of cells, each in one of a finite number of states, updated simultaneously at each time step according to a rule that depends only on the cell’s current state and the states of its immediate neighbors. See: Origins: How Conway’s Game of Life Was Born.
Emergent Behavior A property of a system that arises from the interactions of its components but is not present in any individual component. In Life, the glider “emerges” from the four rules — no single cell is a glider; the glider is a pattern of cell states in time. See: Emergent Behavior: When Simple Rules Make Complex Societies.
Garden of Eden A valid Life configuration that has no predecessor — it cannot be reached from any other configuration by applying the rules for one generation. It can only exist as an initial state. Gardens of Eden must exist (proven mathematically) but are hard to find explicitly. See: The Garden of Eden: Patterns With No Past.
Generation One application of the CA update rule to an entire grid. In Life, all cells are updated simultaneously each generation, based on the grid state in the previous generation. Often used interchangeably with “time step.” See: [Glossary: Update Rule].
Glider The most famous pattern in Conway’s Life: a 5-cell configuration that moves diagonally across the grid, returning to its original shape every 4 generations while displaced one cell diagonally. Gliders are spaceships. See: The Bestiary: A Field Guide to Life’s Creatures.
Glider Gun A pattern that periodically emits gliders (or other spaceships). The Gosper Glider Gun, discovered in 1970, fires a glider every 30 generations and was the first proof that infinite growth is possible in Life. See: Guns: Patterns That Shoot Forever.
Hashlife An algorithm for simulating Life (and other CA) at extreme speeds by memoizing the results of repeated subpatterns. A key insight: if the same 8×8 block appears in two different places at the same time, its future evolution is identical; cache and reuse the result. Enables simulation of patterns for astronomical numbers of generations. See: Interactive sandbox.
Homeostasis In biological CA models, homeostasis refers to a stable internal state maintained despite external perturbations — analogous to a still life that absorbs small disturbances. See: Life Imitating Life: CA and the Biological Sciences.
Influence Field The set of cells that can affect a given cell’s state over n generations — the “causal past light cone” of that cell in CA terms. No influence can travel faster than one cell per generation, so the influence field expands at most one cell per generation in each direction. See: Information Theory and Life.
Life-Like Rule A CA rule on an infinite two-dimensional grid with a Moore neighborhood and two states, described by B/S notation. Life is one of 262,144 life-like rules. See: Beyond Conway: The Universe of Life-Like Rules.
Methuselah A small Life pattern (typically fewer than 15 cells) that takes a disproportionately large number of generations to stabilize. Named for the biblical patriarch. The R-pentomino is the archetypal methuselah. See: Methuselahs: Long-Lived Patterns.
Moore Neighborhood The standard neighborhood for Conway’s Life: the 8 cells immediately surrounding a given cell (N, NE, E, SE, S, SW, W, NW). Named for Edward Moore. Contrasted with the Von Neumann neighborhood (4 cells, no diagonals). See: [Glossary: Von Neumann Neighborhood].
Oscillator A Life pattern that returns to its original state after a fixed number of generations (its period). The simplest is the Blinker (period 2); the most complex known oscillators have periods in the thousands. See: Oscillators: Patterns with a Heartbeat.
Outer Totalistic A class of CA rules (including Life) in which the new state of a cell depends only on its current state and the total (sum) of its neighbors’ states — not on the specific arrangement of neighbors. Outer totalistic rules are a subset of all possible CA rules, and they are the rules described by B/S notation. See: Beyond Conway: The Universe of Life-Like Rules.
Period For an oscillator or spaceship, the number of generations before the pattern returns to its original form (and position, for still lifes; displaced for spaceships). See: Oscillators: Patterns with a Heartbeat.
Probability Field In probabilistic CA extensions, each cell has a probability distribution over states rather than a definite state. Deterministic CA (including Life) are the special case where all probabilities are 0 or 1. See: Chaos and Order: Statistical Properties of Random Soups.
Rule Space The set of all possible CA rules of a given type. For two-state life-like CA (B/S rules), the rule space has 2^18 elements. Exploring rule space — finding which rules produce interesting behavior — has been a major research program. See: Beyond Conway: The Universe of Life-Like Rules.
Self-Replication A CA pattern that produces an exact copy of itself. In most rules this requires careful engineering (as in Life’s 2010 self-replicator); in some rules (HighLife, Replicator) it occurs naturally. See: Self-Replication: When Life Builds Itself.
Spaceship A Life pattern that translates across the grid while returning to its original shape after a fixed period. The Glider (period 4, velocity c/4 diagonal) is the smallest spaceship. See: The Bestiary: A Field Guide to Life’s Creatures.
Speed of Light (c) The maximum speed at which any signal or pattern can propagate in a CA: one cell per generation. In Life, spaceships can travel at c/4 diagonally (the Glider) or c/2 orthogonally (the Lightweight Spaceship). See: Information Theory and Life.
Still Life A Life pattern that does not change: every live cell has 2–3 live neighbors (so it survives) and every dead cell adjacent to the pattern has ≠3 live neighbors (so it stays dead). See: Still Lifes: Patterns That Never Change.
Survival Rule The part of a B/S rule specifying when a live cell stays alive: the set of neighbor counts that permit survival. In Life, this is S23 (2 or 3 live neighbors). See: [Glossary: B/S Notation].
Toroidal Describes a grid whose edges are identified: the right edge connects to the left, the top edge connects to the bottom. The topology of a donut surface. The standard choice for finite Life simulations. See: Flat, Wrapped, and Beyond: Grid Topologies.
Turing Complete A system is Turing complete if it can simulate any Turing machine — if it can compute any computable function given sufficient time and space. Conway’s Life is Turing complete. See: Proof of Concept: Life Is Turing Complete.
Update Rule The function that maps a cell’s current state and neighborhood to its next state. In Life: (alive with 2–3 neighbors) → alive; (dead with exactly 3 neighbors) → alive; otherwise → dead. All cells are updated simultaneously. See: Origins: How Conway’s Game of Life Was Born.
Von Neumann Neighborhood The 4-cell neighborhood consisting of the cells immediately above, below, left, and right of a given cell (no diagonals). Contrasted with the Moore neighborhood (8 cells, including diagonals). Used by von Neumann in his self-replicating CA. See: Von Neumann’s Dream: Self-Replicating Machines.
Wolfram Classes Stephen Wolfram’s classification of CA behavior into four types: Class I (all cells die or become uniform), Class II (simple periodic patterns), Class III (chaotic, random-seeming), Class IV (complex, structured, non-repeating). Life is Class IV. See: Computational Complexity Through a Life-Like Lens.