A genealogy
Each era opened an axis.
The history of state in computing is not a sequence of replacements. It is a walk across the nine axes. Each era moved the field along a dimension the previous one had not yet named. Read in order, the lineage is the stack discovering itself.
The tape and the head
Turing's machine made state explicit. Tape held the data, finite control held the state, the transition function joined them. Every subsequent treatment of state in computing is a refinement of that pair.
Established the formalism axis (F) with its first member: a finite control coupled to unbounded storage.
Finite automata
Mealy and Moore formalized the finite-state machine in two equivalent forms — output on the transition, output on the state. Regular languages followed, and the deterministic / nondeterministic distinction. State at the smallest unit it could be: a label.
Locked in the verifiability axis (V) — finite automata admit decision procedures. Composition (K) was still atomic.
Petri nets
Petri's thesis introduced a graphical formalism for concurrent state — places, transitions, tokens, arcs. Synchronization, conflict, and mutual exclusion became first-class objects in the model rather than corner cases.
Opened the concurrency axis (C) — state that advances in parallel, not in sequence.
The actor
Hewitt proposed actors as the atomic unit of concurrent computation: an actor has private state, processes messages one at a time, and can spawn other actors. State as an architectural boundary, not a shared variable.
Established the isolation axis (I) — the boundary around state is itself the design choice.
Discrete events
Zeigler's DEVS formalized state for simulation — atomic models with time-advance and transition functions, coupled models that compose hierarchically. The first formal account of state that lives in continuous time but moves on discrete events.
Refined composition (K) — coupling as a first-class operation. Foreshadowed the cascade.
Process calculi
Hoare's CSP and Milner's CCS gave concurrent state an algebra. Processes as terms, parallel composition as an operator, communication as synchronization on a channel. Equational reasoning about systems that talk to themselves.
Made concurrent state compositional — the parallel operator a first-class term.
OTP and supervision
Erlang at Ericsson took the actor seriously for telephone switches: lightweight processes, hot code replacement, and the supervision tree as a fault-tolerance discipline. State that survives the failures of its bearer.
Lifted self-reference (A) toward runtime-modifiable. The supervisor was the first widely-used self-aware structure.
Statecharts
Harel extended state machines with depth, orthogonality, and broadcast — sub-states inside super-states, AND-parallel regions, history. The cascade made formal. Statecharts entered UML and became the dominant modeling tool for reactive systems.
Established composition (K) as a full axis: atomic → sequential → AND-parallel → OR-hierarchical.
Mobility and the temporal action
Milner's π-calculus added mobility — channels themselves as values that can move between processes. Lamport's TLA combined temporal logic with action descriptions, giving a single language for stating and checking what a state machine does over time.
Verifiability (V) became model-checked in practice. Composition (K) gained dynamic-structure.
Data-oriented state
The entity-component-system pattern emerged in game development — entities as identifiers, components as data tables, systems as functions over those tables. State organized for the substrate that reads it, not for the abstraction that writes it.
Pulled the formalism axis (F) toward data-orientation; concurrency (C) toward parallel by construction.
Distribution accepted
Helland's "Life Beyond Distributed Transactions" stated the position out loud: at scale, state is partitioned into entities, and there are no cross-entity transactions. seL4 proved a kernel correct against its specification — the first widely-cited example of a state machine whose behavior is mathematically guaranteed.
Concurrency (C) split formally between parallel and distributed. Verifiability (V) reached the substrate.
Reactive hierarchies displace flat machines
Behavior trees took over reactive decision-making in robotics and games — hierarchical, modular, every subtree a building block. Flat finite-state machines were preserved for execution modes; the decision layer became a tree.
Reactivity (R) and composition (K) became orthogonal — the decision tree and the execution machine could be different shapes.
The state machine as orchestrator
Production agent systems converged on the pattern the genealogy had been walking toward: a deterministic state graph in charge of the loop, with model calls as one kind of input among many. The model is a node; the machine is the controller.
Self-reference (A) lifted toward introspectable as the default — the running graph is itself a value that can be inspected, paused, resumed, and rewound.
The reading
The lineage is the stack discovering itself.
Each era did not discard the last; it relocated the default along an axis the field had not yet named. The nine axes are what every one of those moves was a move within. Reading the genealogy forward is reading the structure becoming explicit.