Turing machines and computability

Imagine the simplest possible computer. It is a long strip of paper divided into squares, and a little machine that sits over one square at a time. The machine can read what is in the square, rub it out and write something new, then shuffle one square left or right. That is all it does.

What tells it what to do is a tiny rulebook, something like: "if you are in mood A and you see a 0, write a 1, move right, and switch to mood B." Follow rules like that, one after another, and this bare little machine can do any calculation a real computer can do. Alan Turing dreamed it up in 1936, before real computers existed, to pin down exactly what "computing" means.

The strip-and-rulebook idea, called a Turing machine, is not just a toy. Turing showed you can build one special machine that can imitate any other, just by writing the other machine's rulebook onto its tape. That is the deep idea behind every computer you own: one device that runs any program you feed it.

The twist is what came next. Turing proved there are questions that no program, however clever, can ever answer. The most famous is simple to state: can you write a program that looks at any other program and reliably says whether it will finish or run forever? He proved the answer is no. Some things are simply beyond computing.

A Turing machine has four parts: an endless tape divided into cells, a head that reads and writes one cell, a current state chosen from a small finite list, and a transition table. Each line of the table says, for a given state and the symbol under the head, what to write, which way to move, and which state to enter next. That is the entire machine. The one running above has just three states and yet does real work.

The astonishing claim, the Church-Turing thesis, is that this bare setup can compute anything that is computable at all. Any algorithm you could carry out with pencil, paper and patience, any program in any language, can be done by some Turing machine. Different models of computation people have invented, from lambda calculus to modern programming languages, all turn out to have exactly the same power. So the Turing machine is not one kind of computer among many; it is a definition of what computing is.

From this comes universality. Turing described a single universal machine whose tape holds a description of any other machine plus that machine's input, and which then simulates it faithfully. This is the theoretical blueprint for the general-purpose, stored-program computer: hardware that is fixed, running software that can be anything.

And from the same idea comes a hard limit. Suppose a program H could take any program P and its input and always correctly report whether P halts or runs forever. Build a new program that asks H about itself and then does the opposite of what H predicts. If H says it halts, it loops; if H says it loops, it halts. Either way H is wrong, so H cannot exist. The halting problem is undecidable. No general halt-checker can be written, and many other questions reduce to this one.

Decidable, recognizable, neither. A problem is decidable if some Turing machine always halts and answers correctly, yes or no. It is recognizable, or semi-decidable, if a machine halts and says yes on every yes-instance but may run forever on the no-instances. The halting problem is recognizable but not decidable: you can confirm a program halts by simply running it and waiting, but no machine can guarantee to detect non-halting in finite time. Beyond these lie problems that are not even recognizable.

Diagonalisation and reductions. The halting proof is Cantor's diagonal argument in computational dress: assume an enumeration of all deciders, then construct a machine that differs from every one of them on its own encoding. Once one problem is known undecidable, others fall by reduction. If solving problem B would let you solve the halting problem, then B must be undecidable too. Rice's theorem generalises this: every non-trivial property of the function a program computes is undecidable.

The link to Gödel. This is the computational face of Gödel's incompleteness. Turing answered Hilbert's Entscheidungsproblem, the question of whether a mechanical procedure could decide the truth of any mathematical statement, with a definitive no. Truth outruns any fixed procedure, whether that procedure is a formal proof system or a program. The limits Gödel found in logic and the limits Turing found in computation are two views of the same wall.

Computable is not the same as feasible. Undecidability is about whether a problem can be solved at all, given unlimited time. A separate question is how much time solvable problems take, and that is the domain of complexity theory, where the famous open problem is P versus NP. A problem can be perfectly decidable yet so slow to solve that it is useless in practice. Turing drew the outer boundary of the computable; complexity theory maps the terrain inside it.