State Machines: From a Light Switch to Modern AI

Start with the word state

State is where you are right now, and it decides where you can go next.

A light switch has two states: ON and OFF. When it is ON, the only move is to turn OFF. When it is OFF, the only move is to turn ON.

A state machine is just that, written down properly:

1. A list of possible states
2. A starting state
3. A set of events (inputs)
4. Transitions: "in state A, if event X happens, go to state B"

That is what I meant in my old note when I said state represents everything defined in its space. The current state carries all that matters.

A slightly bigger example: a traffic light

Red can never jump straight to Yellow. The rules of the machine forbid it. That is the real power: illegal situations are impossible by design.

In code, a state machine is often just a lookup table:

transitions = {
    ("red", "timer"): "green",
    ("green", "timer"): "yellow",
    ("yellow", "timer"): "red",
}

state = "red"
for _ in range(4):
    state = transitions[(state, "timer")]
    print(state)   # green, yellow, red, green

The journey through history

Here is the whole trip in one picture, and then we will walk through it slowly.

1930s: Turing machines

Alan Turing (1936) described a machine with a finite set of states plus an endless tape to read and write. The states are the "brain" and the tape is memory. Every computer you use is, in principle, this idea.

1940s: The first link to brains

McCulloch and Pitts (1943) modeled a neuron as a simple on/off unit. Networks of them behave like finite state machines. This is the first bridge between state machines and neural networks. Keep it in mind.

1950s: Formal theory

• Mealy and Moore machines split machines by whether output depends on state plus input (Mealy) or on state alone (Moore).
• Kleene showed that a class of patterns called regular languages matches exactly what finite machines can recognize.
• Chomsky ranked machines by power: finite automata, then pushdown automata (a state machine plus a stack), then Turing machines. Notice the Data Structures Explained connection: a stack is what gives a state machine more memory.

1960s to 1980s: Everyday tools

• Regular expressions compile into state machines. Every search you type into an editor runs one.
• Lexers and compilers use state machines to split code into tokens.
• Network protocols like TCP are state machines: LISTEN -> SYN_RECEIVED -> ESTABLISHED -> FIN_WAIT -> CLOSED.
• Statecharts (Harel, 1987) added nested and parallel states, so big systems like aircraft controls stayed manageable.

1990s to 2000s: Games and hardware

• Game AI: an enemy is Patrol -> Chase -> Attack -> Flee.
• Digital circuits: every CPU control unit is a state machine clocked by a signal.
• Vending machines, elevators, ATMs, washing machines: all state machines.

2010s: The web

• Promises are state machines: pending -> fulfilled or pending -> rejected, and once settled they never change.
• React and Redux manage UI with the same idea. My old note said state management exists to manage the flow of data the user wants to see. A reducer is literally a transition function.

Think of fetching data for a page. It is always in exactly one of four states:

function reducer(state, event) {
  switch (state.status) {
    case "idle":
      if (event === "FETCH") return { status: "loading" };
      break;
    case "loading":
      if (event === "SUCCESS") return { status: "done" };
      if (event === "FAIL") return { status: "error" };
      break;
    case "error":
      if (event === "RETRY") return { status: "loading" };
      break;
  }
  return state; // ignore events that aren't allowed here
}

• XState and similar libraries make this explicit, killing bugs like a button that is "loading" and "error" at once.

The turn: state machines meet neural networks

A neural network on its own is not a state machine. A plain feed-forward net takes an input and gives an output, with no memory. But the moment we want it to handle sequences (text, speech, time), it needs state. The story of modern AI is largely the story of how to carry state well.

Step 1: Recurrent Neural Networks (RNNs)

An RNN reads one item at a time and keeps a hidden state $h_t$:

Compare with the state machine rule: new_state = transition(old_state, input). It is the same shape. The difference is that a classic machine has a handful of named states, while an RNN's state is a big vector of numbers, so it has a huge continuous space of states. The transition function is learned, not hand-written.

Step 2: LSTM and GRU

Plain RNNs forget quickly. LSTM (1997) and GRU added gates: small learned switches deciding what to keep, what to erase, and what to write. Gates work like guarded transitions: "only update the state if this condition holds."

Step 3: Attention and Transformers

Transformers (2017) dropped the step-by-step hidden state and let every token look at every other token. That was faster to train, but the state idea did not disappear:

• When a model generates text, it produces one token at a time, and each new token depends on everything so far. That is a machine moving through states.
• The KV cache is the machine's memory of the past. It grows with every token, and its cost is why long conversations get expensive.

Step 4: The return of state: State Space Models

Because the cache grows without limit, researchers went back to a fixed-size state. State Space Models (S4, then Mamba) use an update like:

This comes straight from control theory, a cousin of state machines from the 1960s. The state stays the same size no matter how long the input is. It is fast for long sequences, and the older idea is back in cutting-edge models.

Step 5: AI agents are explicit state machines

Modern agent systems make the state machine visible:

Frameworks like LangGraph model an agent as nodes (states) and edges (transitions), with a shared state object passed along. The model chooses the next transition, and the state machine keeps it from wandering into nonsense.

Also: Reinforcement learning

An RL agent lives in an environment with states, takes actions, and moves to new states for rewards. This is a Markov Decision Process, a state machine where transitions are chosen and rewarded. It trained game-playing AIs, and it fine-tunes chat models today.

The same question, a bigger state

Why it keeps coming back