A Turing machine trades the PDA's stack for something more general: an infinite tape it can both read from and write to, moving the read/write head one cell left or right on every step. That's a small change on paper, but it's enough to simulate any algorithm — the Church-Turing thesis holds that nothing "effectively computable" lies beyond what a Turing machine can compute.

The formal definition

A (single-tape) TM is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject): an input alphabet Σ, a (larger) tape alphabet Γ that includes a blank symbol, and a transition function δ: Q × Γ → Q × Γ × {L, R} — read a symbol, write a symbol, move the head. Transitions in the simulator are written read/write,direction, e.g. 0/X,R. A multi-tape machine runs several tapes and heads in lockstep, one read/write,direction segment per tape, joined with ;.

Worked example: deciding 0ⁿ1ⁿ

This is the same language the aⁿbⁿ PDA recognizes in the pushdown automata lesson — but a Turing machine decides it with a completely different mechanism: no stack, just repeatedly crossing off one 0 and its matching 1 until nothing (or a mismatch) is left.

TM deciding {0ⁿ1ⁿ : n ≥ 0}

Open in full simulator ↗

The strategy, state by state: q0 finds the leftmost uncrossed 0, marks it X, and moves right to hunt for a matching 1 — or, if every 0 is already crossed (all that's left is Ys), jumps ahead to the final check. q1 skims right over 0s and already-matched Ys until it hits a 1, marks that Y, and turns around. q2 walks back left over 0s and Ys until it finds the X it started from, then moves one step right and hands control back to q0 for the next round. Once q0 finds only Ys (every 0 matched), q3 confirms nothing but Ys and then blank remain, and accepts.

Try 0011 (accepts), and then 0110 or 10 (both reject — trace the head to see exactly where the machine gets stuck with no applicable move, which is how a TM rejects).