Turing Machines & Automata: Interactive
A hands‑on tour of the core models of computation: finite automata (tiny, fast pattern checkers) and Turing machines (general, step‑by‑step algorithms). Each comes with a live visual and a breakdown of the parts.
Hover here for connections to companion pieces.
Finite Automata (DFA)
A DFA is a small machine that reads an input left to right and keeps only a state. The classic five‑tuple is $(Q,\Sigma,\delta,q_0,F)$: states $Q$, alphabet $\Sigma$, transition function $\delta$, start $q_0$, accepting set $F$. related
Below is a DFA that accepts exactly the binary strings with an even number of 1s. Shift your attention between the tape and the highlighted state: the machine stores only “parity so far”. That’s the trick: limited memory, fast decisions.
state=q0
| $\delta$ transitions | ||
|---|---|---|
| state | on 0 | on 1 |
| q0 (accept) | q0 | q1 |
| q1 | q1 | q0 |
From first principles: choose an alphabet $\Sigma$ (here $\{0,1\}$). Words are finite strings over $\Sigma$ (the set $\Sigma^*$), including the empty word $\varepsilon$. A DFA processes a word one symbol at a time. The transition extends to whole words via $$\hat{\delta}(q,\varepsilon)=q,\qquad \hat{\delta}(q,aw)=\hat{\delta}(\,\delta(q,a),\,w\,),$$ and a word $w$ is accepted precisely when $\hat{\delta}(q_0,w)\in F$.
What the state really is: a compact summary of “everything about the prefix that still matters”. For parity, that summary is a single bit: even/odd so far. For “ends with 01”, it’s whether your last one or two symbols were 0 then 1. If no finite summary exists, the language is not regular.
Terms in the formula: $Q=\{q0,q1\}$; $\Sigma=\{0,1\}$; $\delta(q,\sigma)$ picks the next state; $q_0=q0$ is the start; $F=\{q0\}$ accepts even‑parity strings.
Deterministic vs nondeterministic: an NFA can branch, but you can track all branches as a set of states (subset construction). This is why NFAs and DFAs recognize the same class (regular languages). Kleene showed regular expressions, NFAs, and DFAs are equivalent; DFAs are closed under union/intersection (product) and, when total, complement (swap accepts).
Context: Kleene and others used such automata to formalize “regular patterns”. They are fast and simple, but they can’t count arbitrarily far; that needs a stack (pushdown) or a tape (Turing).
Turing Machines
A Turing machine is an idealized paper‑and‑pencil computer: a tape of symbols, a head that reads/writes, and a finite state control. Formally, $(Q,\Gamma,\Sigma,\delta,q_0,q_{acc},q_{rej})$ with tape alphabet $\Gamma$, input alphabet $\Sigma\subseteq\Gamma$, and $\delta$ mapping $(\text{state},\text{symbol})$ to $(\text{write},\text{move},\text{next})$.
Below: a tiny program that increments a unary number (a run of 1’s). It moves right over 1’s until it finds blank, writes a 1, and halts. Simple, but you can see the head walking, the local edit, and the stop: exactly how bigger programs behave.
state=q0
Program (rules):
Terms in the formula: $Q=\{q0,qh\}$; $\Gamma=\{1,\_\}$; $\Sigma=\{1\}$; $q_0=q0$; $q_{acc}=qh$; $\delta(q0,1)=(1,R,q0)$, $\delta(q0,\_)=(1,S,qh)$. The head writes, moves L/R/S (stay), and changes state until it halts.
Context: Turing’s 1936 paper used these machines to pin down “effective procedure”. The surprising part is how little you need to get general computation: a finite control and a long enough tape.
What Languages These Machines Recognize
Automata sit in a simple ladder. A DFA recognizes exactly the regular languages (think: patterns with no unbounded counting). Add a stack and you get a pushdown automaton (PDA) for context‑free languages such as balanced parentheses. Give a machine a full read/write tape and you get Turing machines that can simulate any algorithm we know how to write.
Two helpful intuitions: (1) Regular languages have finitely many “situations that matter” (Myhill–Nerode equivalence classes). (2) A single unbounded counter (a stack) lets you match opens with closes, but not two counts at once (you need more memory for $a^n b^n c^n$). These pictures are the memory you’re allowed to carry.
Build a DFA
Click “Add state” and place a few nodes. Choose a start, toggle accepting states, and add transitions with symbols from your alphabet. Enter an input and step through. The highlight shows the current state; acceptance requires halting in an accepting state with all input consumed.
…
Parts: $Q$ = your states; $\Sigma$ = symbols you use in transitions; $\delta$ = your arrows; $q_0$ = start; $F$ = states you toggled to accept.
Tip: Try to build a DFA for strings over {0,1} that end with 01. How many states do you need? Where does the machine store “I just saw a 0”?
Pushdown Automaton (Balanced Parentheses)
A PDA is a finite control plus a stack. Here we check balanced parentheses. Read '(' and push; read ')' and pop; reject on underflow; accept if the stack is empty at the end. The stack is the one unbounded memory you carry.
…
Parts: states $Q=\{q\}$ (one is enough here), stack alphabet $\Gamma=\{\$, (\}$ with base symbol $\$$; transition pushes on '(' and pops on ')' if possible; acceptance when input ends and top is $\$$.
Try adding a stray ')' mid‑string and step: the pop fails and the PDA rejects immediately. That’s the stack telling you “too many closes”.
Edit a Turing Program
Write rules as lines like q0,1 -> 1,R,q0 and q0,_ -> 1,S,qh. The machine reads the current symbol, writes, moves L/R/S (stay), and changes state. Halt when no rule matches or you reach a designated halt state like qh.
…
Terms: each line is $\delta(q,\sigma)=(\sigma',\text{move},q')$. Use '_' for blank. You can add states freely; halting occurs when no rule applies or you reach a halt state you designate (e.g., qh).
- DFAs here connect to NFAs: NFAs from First Principles (ε‑moves, determinize).
- State diagrams echo linear maps & basis views from the Toolkit.
- See also: Computation & Automata path.