Why Some Questions Have No Answer, Even for the Smartest Machine
The Puzzle That No One Could Solve
In 1936, a shy twenty-four-year-old mathematician named Alan Turing (1912–1954) sat down to solve a puzzle that had stumped the world’s greatest minds. The puzzle was called the Entscheidungsproblem — a German word meaning “decision problem.” Could one create a single, step-by-step procedure that would decide, for any statement in mathematical logic, whether it was provable? If such a method existed, a machine could, in theory, answer every yes‑or‑no question in mathematics.
The leading mathematicians of the day hoped the answer was yes. Turing suspected otherwise. But to even ask the question precisely, he first had to say exactly what “computing” meant. That led him to invent an imaginary device that is now the foundation of computer science: the Turing machine.
A Machine Made of Paper and Rules
A Turing machine is not a real machine; it is a thought‑experiment. Imagine a long strip of paper — a tape — divided into squares. Each square can hold a symbol, like 0 or 1, or be blank. A read‑write head scans one square at a time. Inside the machine there is a list of states (think of them as moods or memories) and a table of transition rules. A rule says: if you are in this state and you read that symbol, then write a new symbol, move one square left or right, and switch to a new state.
The machine is deterministic — at every moment, the current symbol and state completely decide what happens next. It keeps moving and writing until, perhaps, it halts. (Turing sometimes called it an automatic machine.) The tape is as long as you need it to be, and the machine can take as much time as it needs. These assumptions are not realistic — no real computer has infinite memory or infinite time — but they make sure we don’t call something “uncomputable” just because we ran out of room or patience.
A function is called Turing‑computable if there is some Turing machine that, starting with the input on the tape, eventually writes the correct output and halts. Turing argued that any problem that can be solved by a human following a finite set of clear, mechanical steps can be solved by a Turing machine. This is the core of what later became called the Church‑Turing thesis.
The Machine That Reads Minds
Turing then did something even more remarkable: he designed a single Turing machine that could imitate any other Turing machine. He called it the universal Turing machine. Here’s the idea: you write a description of another machine’s rules and its input onto the universal machine’s tape. Then the universal machine reads that description, decodes it, and precisely mimics what the original machine would do.
This is exactly what a modern programmable computer does. Your phone or laptop is a universal machine: it does not have separate hardware for a calculator, a video game, and a web browser. Instead, it has one general‑purpose processor that reads a program (the app) and runs it. Turing’s insight was that a single, relatively simple device could, in principle, compute anything that is computable at all — provided you give it the right tape.
The universal machine made the Church‑Turing thesis concrete: if a problem is computable, then a universal Turing machine can handle it. If a universal Turing machine cannot solve it, then it is uncomputable — beyond the reach of any finite procedure.
The Problem That Breaks the Machine
If the universal Turing machine was the good news, what came next was the bombshell. Turing used his own model to prove that there are well‑defined problems that no Turing machine can solve — not even the universal machine. The most famous is the halting problem.
Here’s the question: given a description of any Turing machine and an input, can a machine decide, without actually running the program forever, whether that machine will eventually halt? In other words, could you build a perfect “halt‑or‑loop” detector that works for every possible program?
Turing showed the answer is no. His proof is a twist of self‑reference. Suppose, for the sake of argument, that a mythical machine H can decide the halting problem. Now build a trickster machine D. When given its own description as input, D asks H what D will do. If H says “it will halt”, D loops forever; if H says “it will loop”, D halts. So D does the opposite of whatever H predicts. That creates a contradiction: H cannot be right about D. Therefore, H cannot exist. No Turing machine can solve the halting problem.
Because the halting problem is unsolvable, and Turing showed that a solution to the Entscheidungsproblem would give a solution to the halting problem, the dream of a single mathematical truth‑detector collapsed. Some questions are forever undecidable by any step‑by‑step procedure.
Why Everyone Agreed Turing Was Right
Turing was not alone. Around the same time, the American logician Alonzo Church (1903–1995) developed a very different system called the lambda calculus. It used rewriting rules on symbols instead of tapes and heads. Emil Post (1897–1954) created his own kind of abstract machines and production systems. To everyone’s surprise, all these models turned out to be equivalent: they could compute exactly the same set of functions as Turing machines. This strengthened the conviction that there is a natural, objective boundary between the computable and the uncomputable.
Today, the Church‑Turing thesis is not a theorem — you cannot prove that a vague idea like “effectively computable” matches a formal model — but it has never been overturned. Every attempt to find a computable function that a Turing machine cannot capture has failed. That gives us enormous confidence that when we say “uncomputable,” we mean a real and permanent limit.
What This Means for Your Phone
You carry a universal Turing machine in your pocket. Your smartphone, laptop, and game console all work on the very principle Turing described: a general‑purpose device that reads a program and executes it. The limits he discovered are just as real today. No virus scanner can perfectly determine whether every piece of code is safe, because that would require solving the halting problem. No artificial intelligence can answer every question about what another computer program will do. The line between solvable and unsolvable is not a temporary engineering glitch; it is a fact of mathematics.
Because Turing drew that line, we know exactly what computers can — and cannot — ever do. It is a humbling reminder that even the smartest machine, with infinite time and memory, must eventually stop.
Think about it
- Imagine a computer program that takes another program and tries to decide whether it will eventually stop or run forever. Why might such a program be impossible to write? Try to think of a clever trick that would break it.
- If a modern supercomputer could run every possible program at once, would it still be stuck on the halting problem? Why or why not?
- Why does it matter that some perfectly clear questions can never be answered by a machine, no matter how much time and memory it has?
