Turing Machines

A finite-state machine is powerful, but it has one crippling weakness: it can only ever remember which state it is in. That is a fixed, finite amount of memory. Ask an FSM to check whether a string of brackets is balanced — (((\ldots))) with the same number each side — and it simply cannot, because it would need to count arbitrarily high, and it has nowhere to keep the count.

In 1936, long before any electronic computer existed, the mathematician Alan Turing asked a deceptively simple question: what does it actually mean for something to be "computable"? To answer it he invented an imaginary machine — stripped down to the barest possible parts — and then argued that anything a human could compute by following rules on paper, this machine could compute too. That machine is now called a Turing machine, and it is the theoretical ancestor of every computer you have ever used.

The four parts

A Turing machine is astonishingly simple. It has just four ingredients:

an infinite tape divided into cells, each holding one symbol (for us: 0, 1, or blank). This is the key upgrade over an FSM — unlimited read/write memory;
a read/write head that sits over exactly one cell — it can read the symbol there, overwrite it, and then move one cell left or right;
a finite set of states (just like an FSM) — the machine's "frame of mind";
a transition rule (or transition table) — the program.

At every tick the machine looks at just two things — its current state and the symbol under the head — and the transition rule tells it three things to do:

(\text{state},\ \text{symbol}) \longrightarrow (\text{symbol to write},\ \text{move L or R},\ \text{new state})

That is the whole machine. It writes a symbol, nudges the head one step, and changes its mind about what state it is in — over and over — until it reaches a halting state.

Watching one run: add 1 to a binary number

Let's build a real (tiny) Turing machine that adds one to a binary number. The idea is exactly how you add 1 by hand: start at the rightmost bit and carry leftwards. Every 1 becomes a 0 (and carries), and the first 0 becomes a 1 (and the carry stops). Here it is turning 1011 (that's 11) into 1100 (that's 12). Step through it:

Read top to bottom, each row is the tape after one move. The ▲ marks where the head is. Notice how little the machine "knows" at any moment — just its state and the one symbol beneath it — yet the carry ripples correctly all the way along.

The program, written out

The machine above uses two states. addOne is the "still carrying" state (it assumes it must add 1 to the current bit); reaching halt means it is finished. Here is the entire transition table — the machine's whole "program":

State Read Write Move Next state ------------------------------------------------ addOne 1 0 Left addOne (1 + carry = 0, carry on) addOne 0 1 — halt (0 + carry = 1, carry stops) addOne blank 1 — halt (ran off the end: write the new 1)

Three lines of rules, and it will correctly increment a binary number of any length — because the tape is unlimited, the number can be as long as it likes. Try running a full simulator below. It prints the tape after every step so you can watch the head crawl along. Change the starting number and press Run:

type Sym = "0" | "1" | "_"; // "_" is the blank cell interface Rule { write: Sym; move: number; next: string; } // The transition table: state -> symbol -> what to do. const delta: Record<string, Record<string, Rule>> = { // scan right to the end of the number, then start carrying scanRight: { "0": { write: "0", move: +1, next: "scanRight" }, "1": { write: "1", move: +1, next: "scanRight" }, "_": { write: "_", move: -1, next: "addOne" }, }, // add 1 with carry, moving leftwards addOne: { "1": { write: "0", move: -1, next: "addOne" }, "0": { write: "1", move: 0, next: "halt" }, "_": { write: "1", move: 0, next: "halt" }, }, }; const tape: Sym[] = ("1011" + "_").split("") as Sym[]; // input, plus a blank let head = 0; let state = "scanRight"; let guard = 0; while (state !== "halt" && guard++ < 50) { const sym: Sym = tape[head] ?? "_"; const rule = delta[state][sym]; tape[head] = rule.write; console.log(state.padEnd(9) + " |" + tape.join("") + "| head at " + head); head += rule.move; state = rule.next; } console.log("HALTED. Result = " + tape.join("").replace(/_/g, ""));

Why this beats a finite-state machine

Line up the two models. An FSM has states and reads input — and so does a Turing machine. The one difference is the tape:

an FSM reads its input once, left to right, and can never write anything down or look back. Its only memory is the current state — a fixed, finite amount;
a Turing machine can move both ways and write on the tape, using it as unlimited scratch paper. It can count as high as it likes, remember arbitrarily much, and revisit earlier work.

That unlimited scratch paper is the entire jump in power. The balanced-brackets problem the FSM choked on? A Turing machine solves it easily — it just tallies the brackets on the tape. Anything an FSM can do, a Turing machine can do; but a Turing machine can do vastly more.

It is tempting to think a Turing machine is powerful because it is fast or complicated — it is neither. It is glacially slow and gloriously stupid, shuffling one cell at a time. Its power comes entirely from one thing: the tape is infinite. That unlimited memory is the whole difference between it and a finite-state machine.

And a second trap: a Turing machine is not a machine you would ever build. An infinite tape cannot exist. It is a mathematical model for reasoning about what can and cannot be computed — a thinking tool, not a product. When we say a real computer is "Turing-complete," we mean it can do anything a Turing machine can, ignoring the practical limit of finite memory.

The astonishing claim

Turing's machine looks far too feeble to matter. Yet the deep result — believed by essentially every computer scientist — is this:

Anything that can be computed at all can be computed by a Turing machine. Every algorithm, every program, every mechanical procedure — no matter the language or the hardware — can be carried out by some Turing machine.
It is a thesis, not a proof: it links the fuzzy human idea of "an effective procedure" to the precise mathematical idea of a Turing machine. No one has ever found a counterexample.

This is why the Turing machine is the yardstick of computation. If you want to know whether something is computable, you ask: could a Turing machine do it? (And famously, Turing also found problems — like the halting problem — that no Turing machine can solve, proving some things are simply uncomputable.)

Turing went one step further and designed a universal Turing machine: a single Turing machine that takes, as input on its tape, a description of any other Turing machine plus that machine's input — and then faithfully simulates it. One fixed machine that can become any machine, just by feeding it a different "program" as data.

Look at what that is: a machine whose behaviour is set by a program stored in its own memory alongside its data. That is the stored-program computer — the blueprint behind every phone, laptop and server on Earth — sketched out a decade before the first one was built.