Why Can't Computers Solve Every Problem?
The Man Who Wanted a Machine for All Answers
In 1928, the mathematician David Hilbert (1862–1943) stood before the world’s greatest logicians and made a bold demand. He believed that all of mathematics could be written in a precise formal language, like a code with no ambiguity. Once that was done, he wanted a decision procedure — a foolproof, step-by-step recipe that could tell you, for any mathematical claim, whether it was true or false. He called this the Entscheidungsproblem (German for “decision problem”). In his textbook, he and Wilhelm Ackermann called it “the main problem of mathematical logic.” Hilbert was not asking for a supercomputer; he was asking whether such a recipe could exist at all, in principle.
For a moment, it seemed close. In 1930, the young Austrian logician Kurt Gödel (1906–1978) proved that every valid statement in first-order logic (a powerful language for math) could be reached by a mechanical list of proofs. Imagine a robot that writes down all possible strings of symbols, checks each one to see if it’s a correct proof, and adds the conclusion to a giant scroll. Gödel showed that if a statement is truly valid, that robot will eventually write it on the scroll. The trouble was, if a statement was not valid, the robot might never tell you. It would just keep scribbling forever, never saying “no.”
Hilbert wanted a method that could also say “no” correctly, for every possible statement. That seemed a small extra step, but no one could find it.
Turing’s Paper Strip: The Simplest Machine That Could Think
In 1936, a quiet, athletic British student named Alan Turing (1912–1954) attacked the problem from a startling angle. Instead of trying to build a real machine, he imagined the simplest possible device that could still do any calculation. He described a Turing machine: a thin, infinite strip of paper tape divided into cells, each holding a symbol (like 0, 1, or blank). A read-write head could scan one cell at a time, read the symbol, and, based on a short list of internal states and simple rules, write a new symbol, move left or right one cell, and change state. Even with just this modest setup, Turing argued, his machine could carry out any step-by-step computation anyone could ever dream up.
Around the same time, Alonzo Church (1903–1995) in the United States defined a system called the lambda calculus, and other mathematicians proposed their own models. To everyone’s amazement, all these wildly different systems turned out to be exactly equal in power. Anything computable in one was computable in the others. This led to the Church-Turing Thesis: the intuitive idea of “computable in principle” is perfectly captured by Turing machines (and their equivalents). It’s not a mathematical theorem you can prove; it’s a deep belief that no mechanical procedure will ever go beyond them.
Turing took an extra step that still shapes your daily life. He showed that one special machine could read the description of any other Turing machine and then simulate it exactly. This universal Turing machine is the ancestor of today’s computers. Your laptop doesn’t need a new chip for every app; a single general-purpose processor runs whatever program you feed it. Turing saw that well before anyone had built a digital computer.
The Trap That Never Shuts: The Halting Problem
Even before his universal machine was fully grasped, Turing noticed something ominous. Some Turing machines, on some inputs, simply never halt. They loop forever, or wander to the right looking for a symbol that never comes. Could we build a master program that examines any Turing machine and its input and correctly announces “yes, it will eventually stop” or “no, it will run forever”? This became the famous halting problem.
Turing proved that no such master program can exist. Here’s the idea. First, imagine we could list every possible Turing machine in order: M₁, M₂, M₃, … . Now consider a special set, which we’ll call K: the collection of all numbers n for which M_n eventually halts when you feed it its own number n as input. (That sounds twisted but it’s perfectly legal — each machine is just a set of instructions that can be written as a number.) The set K is recursively enumerable (r.e.): you can write a program that simulates each M_n(n) one by one and, whenever a machine stops, adds its number to a list. But being r.e. doesn’t guarantee that you can ever say “no” with certainty for numbers not in K; you might wait forever and never hear back.
Now suppose, for a moment, that there is a program that can decide membership in K — one that, for any number n, correctly outputs “yes” if n is in K and “no” if it is not. Then you could build a devilish counter-machine: when faced with a number d, it would secretly ask the decision program what would happen if M_d ran on input d. If the answer is “yes, M_d(d) halts,” the counter-machine deliberately loops forever. If the answer is “no, M_d(d) doesn’t halt,” the counter-machine immediately stops. Since this cunning machine must itself be one of the machines on our list — say, M_k for some k — ask what happens when it runs on its own number k. If M_k(k) halts, then by its own design it loops forever; if it doesn’t halt, then it halts. Contradiction. Therefore, the decision program we imagined cannot exist. The halting problem is undecidable: no finite, mechanical procedure can always tell you whether an arbitrary program will stop.
That single result smashed Hilbert’s dream. If you can’t even decide whether a computation will finish, you certainly can’t build an all-knowing mathematical truth machine. But the wreckage cleared the ground for modern computer science.
When Possible Isn’t Good Enough: The Speed of Thinking
Even when a problem is decidable, there is a second, practical wall. How long does it take? In the 1960s, researchers began sorting problems by their computational complexity. They classified them by how the number of steps grows as the input gets larger. A problem solvable in polynomial time — that is, in roughly n*c steps for an input of size n, where c is some fixed number — belongs to the class P. These are thought of as feasibly computable problems: doubling the input length only multiplies the work by a manageable constant factor. Sorting a list or finding the shortest path on a map lives in P.
But many puzzles we care about, like packing suitcases, scheduling classes, or cracking codes, seem to be harder. They sit in a class called NP (nondeterministic polynomial time). The name is clunky, but the idea is simple: if someone hands you a candidate solution, you can check whether it’s correct in polynomial time. Think of a jigsaw puzzle: scrambling together 1,000 pieces is agony, but if a friend shows you a completed picture, you can quickly see that every piece fits. NP is precisely the class of problems that have short proofs of “yes” answers.
The million-dollar question — literally, one of the Clay Millennium Problems — is whether P equals NP. Are all those jigsaw-puzzle-style problems actually solvable as quickly as they are checkable, if only we were clever enough? Nobody knows. Most experts strongly suspect P ≠ NP, but no one has proved it.
The Hardest Puzzles on Earth
Inside NP lives a gang of fearsomely difficult problems called NP-complete. A problem is NP-complete if it belongs to NP and every other problem in NP can be boiled down to it by a fast, polynomial-time recipe. In 1971, Stephen Cook proved that SAT, the Boolean satisfiability problem, is NP-complete. Given a sentence built from variables like “x AND NOT y OR z”, SAT asks: can you assign true/false values to make the whole sentence true? It sounds dry, but SAT is a ghost that haunts planning, circuit design, and AI.
Many natural problems — from coloring maps without using the same color for adjacent countries, to finding a subset of numbers that sums exactly to a target — turn out to be NP-complete. If you found a fast algorithm for any one of them, you’d instantly get a fast algorithm for all of NP. Because no such algorithm is known, these problems are widely believed to require exponential time, making them impractical for large inputs.
Yet researchers noticed something strange and beautiful. When they studied whole families of “constraint satisfaction problems” — where you have variables and a list of allowed patterns — these families seem to split sharply: each is either solvable in P or is NP-complete. No muddy middle. This dichotomy, conjectured by Tomás Feder and Moshe Vardi and eventually proved independently by Andrei Bulatov and Dmitriy Zhuk in 2017, tells us that among a huge class of puzzles, there are no eternal intermediate-hard problems. Either a puzzle-type is gentle, or it’s as tough as SAT.
Limits That Make Us Cleverer
Why should a twelve-year-old care about undecidability and NP-completeness? Because these invisible fences shape the digital world you live in. Your phone’s voice assistant doesn’t try to understand language perfectly — that would be an undecidable mess — but it uses approximate, fast algorithms trained on mountains of data. Game designers know that finding the absolute best move in chess is too slow, so they use clever heuristics that make the game fun and fast. Every time a compiler warns you about an infinite loop, it’s skirting the edge of the halting problem: it can spot many common mistakes, but it knows it can never catch them all.
The story that started with Hilbert’s dream and Turing’s paper strip doesn’t end in failure. It ends in a map of the knowable. Because we understand that some questions are unanswerable, we focus on the ones we can answer — and on building breathtaking bridges between what a machine can compute and what a human needs. The limits of computation are not just walls; they are signposts pointing toward the most creative solutions.
Think about it
- If you had a program that could perfectly predict whether any other program would stop, could you use it to build a program that tricks it? What would that trick program look like?
- Think of a video game puzzle where checking a solution is quick, but finding one from scratch is hard. Can you imagine a real-life school problem with the same property?
- Knowing that some problems are impossible for computers, does that change how you think about what your phone or laptop can do? Why or why not?
