Finite automata have no memory beyond their current state. Pushdown automata add a stack: unbounded, but restricted to last in, first out access. A Turing machine removes the restriction entirely: an infinite tape that can be read, written, and moved across in either direction. That small change turns out to be enough to define what "computable" means at all.

The Formal Model

A Turing machine is defined by seven components, (Q, Σ, Γ, δ, q0, q_accept, q_reject), where Γ is the tape alphabet (including a blank symbol) and the transition function δ: Q × Γ → Q × Γ × {L, R} reads the symbol under the head, writes a new symbol in its place, moves the head one cell left or right, and changes state, all in a single step.

What Makes It Different

A PDA can only ever look at the top of its stack, and can only add or remove from that one end. A Turing machine's head can revisit any cell it has already written, in either direction, as many times as it needs. That's the whole trick: unrestricted read/write access to unbounded memory is exactly what lets a Turing machine simulate any algorithm, a claim credited to Alonzo Church and Alan Turing.

Worked Example: Incrementing a Binary Number

To add 1 to a binary string on the tape:

Move right to the end of the number (the first blank cell).
Move one cell left, onto the last digit.
If the digit is 0, write 1 and halt. No carry needed.
If the digit is 1, write 0 (the carry), move left, and repeat the check on the previous digit.
If the carry runs off the left end of the number, write a new leading 1 and halt.

Every step just reads a symbol, writes a symbol, and moves the head, but chaining these together implements ordinary binary addition, which is the general pattern for every Turing machine construction: break the algorithm into reads and writes on a single cell.

Multiple Tapes and Nondeterministic Variants

Turing machines with multiple tapes (several independent tapes and heads) and nondeterministic Turing machines can both be simulated by an ordinary deterministic machine with a single tape, with at most a polynomial slowdown for the multiple tape case and an exponential one for the nondeterministic case. They're more convenient to design with, but they don't recognize any language a basic Turing machine couldn't.

The Limits: Decidability

Not every language can be decided by a Turing machine. The most famous example is the halting problem: no Turing machine can decide, for every machine/input pair, whether that machine eventually halts. This isn't a limitation of cleverness; Turing proved it's mathematically impossible for any algorithm to exist. It's also the reason "Turing complete" is the ceiling: nothing more powerful, in this sense, exists to reach for.

Try It Yourself

Build the binary increment machine above on the canvas and step through it one move at a time. The tape panel shows the head position and every write as it happens, which is the easiest way to build intuition for how a Turing machine "thinks."