Is There a Problem No Computer Can Ever Solve?

The Grand Search for a Decision Machine

In 1928, the famous mathematician David Hilbert (1862–1943) walked into a lecture hall and asked a question so big it would rattle the world. His query: Is there a single mechanical procedure — a cookbook of logical steps — that can decide whether any mathematical statement is true or false? If you handed the machine a claim like “Every even number greater than 2 is the sum of two primes,” it would, after finitely many operations, spit out a yes or a no. Hilbert called this dream the Entscheidungsproblem, German for “decision problem.”

Many mathematicians believed the answer had to be yes. After all, humans seemed to follow rules to prove things. Couldn’t those rules be boiled down to a perfect, step‑by‑step algorithm? But to settle the question, they first had to pin down exactly what a “step‑by‑step procedure” meant. That chase sent them deep into a world of recipes that build themselves — a concept known as recursion.

Recipes That Build Themselves

Think about how you might explain addition to someone who only knows the number 0 and how to add 1. You could say: (i) (x + 0 = x); (ii) (x + (y+1) = (x+y) + 1). That’s a recursive definition: you define a function by making it depend on simpler cases of itself, eventually bottoming out at a base case. The 19th‑century thinkers Hermann Grassmann (1809–1877) and Charles Sanders Peirce (1839–1914) wrote down exactly these kinds of rules for addition and multiplication. Later, Richard Dedekind (1831–1916) showed you could build the whole arithmetic of numbers on such foundations.

A primitive recursive function is a function you can build from three building blocks: the constant zero function, the “add one” (successor) function, and projection functions that just pick out one of their inputs. You then combine them using two operations: composition (plugging one function’s output into another) and primitive recursion itself — exactly the pattern you used for addition. Under this scheme, multiplication, exponentiation, the Fibonacci sequence, and almost every everyday math function you can think of is primitive recursive. You can trace the steps with a pencil and always reach an answer. So far, “computable” seemed to line up neatly with “primitive recursive.”

The Function That Outgrows All Recipes

But then a surprise crashed the party. In the late 1920s, Wilhelm Ackermann (1896–1962) cooked up a function that is clearly computable — you can describe how to work it out — yet it cannot be captured by any primitive recursive definition. The Ackermann-Péter function (later refined by Rózsa Péter, 1905–1977) starts innocently: its first few rows look like addition, multiplication, exponentiation. But then it accelerates. By the time you reach row 4, the numbers explode so fast that even writing them down would fill the universe. Still, you can compute them, following a more powerful kind of recursion that lets the recipe feed on itself in new ways.

This showed that the class of primitive recursive functions was too small. It didn’t include every function a human (or machine) could calculate by following clear instructions. So mathematicians widened the net. Kurt Gödel (1906–1978), building on an idea from Jacques Herbrand (1908–1931), defined the general recursive functions. Later, Alonzo Church (1903–1995) and Alan Turing (1912–1954) each described their own formal models — the lambda calculus and Turing machines. Amazingly, all these different schemes captured exactly the same set of computable functions. This convergence led to Church’s Thesis (proposed by Church, but ultimately accepted by Turing and others): a function is effectively computable by a finite mechanical procedure if and only if it is general recursive (or Turing‑computable). In plain English: the fuzzy idea of “follow a recipe” had a precise mathematical mirror.

The Halting Problem: An Unanswerable Question

With a clear notion of computability in hand, you might think Hilbert’s decision problem could finally be cracked. Turing, however, proved that the grand dream was impossible. He did it by asking a simpler‑sounding question first: Can a machine look at a program and its input and reliably tell whether that program will ever finish running, or whether it will spin forever in an endless loop? This is the Halting Problem.

Turing imagined a master program, H, that takes the code of any other program P and an input X, and always answers “Yes, P halts” or “No, it loops forever.” Then he crafted a clever, self‑referential prank: build a program D that feeds itself to H and does the opposite of whatever H predicts. If H says D will halt, D deliberately goes into an eternal loop; if H says D will loop, D halts. So H cannot exist — the Halting Problem is undecidable.

Because Turing could translate any decision problem about mathematical formulas into a halting‑style problem, he showed that the original Entscheidungsproblem is also undecidable. No cookbook, no computer, no amount of cleverness can build a sure‑fire truth‑detector for all of mathematics. There will always be questions that slip through the net.

The Ladder of Harder and Harder Problems

You might think the story ends there: some problems are undecidable, and that’s that. But Emil Post (1897–1954) and Stephen Cole Kleene (1909–1994) discovered something stranger. Not all undecidable questions are equally hard. There is a whole ladder of difficulty — the Turing degrees.

Imagine you had an oracle that could answer the Halting Problem in one magic glance. You’d still be stuck on other, harder problems. Even with that oracle, you couldn’t decide whether every program ever stops running for that oracle’s halting problem. And so on, forever. The Turing degrees form an infinite, branching hierarchy. Some problems are so stubborn that you could climb rung after rung and never reach them. Post asked whether there is any c.e. (computably enumerable) degree strictly between the computable sets and the Halting Problem’s degree — a question that took years of ingenious “priority method” constructions to answer with a yes. The landscape of unsolvability turned out to be much richer than anyone expected.

Why Limits Are Good for Us

These discoveries from the 1930s aren’t dusty museum pieces. They are alive every time you use a computer. Because the Halting Problem is undecidable, there is no perfect antivirus that can spot every possible piece of malicious code without fail. There is no program that can always tell you whether your homework‑checking script will crash before it runs. The limits are built into logic itself, not just the limits of today’s hardware.

Yet these limits also guide us. Knowing that a question is undecidable means we can stop hunting for an all‑knowing algorithm and instead search for clever approximations or shorter‑term solutions. Moreover, the fact that human mathematicians can sometimes see truths that no mechanical procedure can catch — as Gödel’s famous Incompleteness Theorem suggests — keeps a space for human insight. The 1930s hunt for a perfect decision machine didn’t end with a machine that could answer everything. It ended with a map of what can never be fully mapped, and that, paradoxically, makes our own thinking all the more valuable.

Think about it

1. If you could build a machine that solves the Halting Problem for every ordinary program you can write today, would you trust it to prove that a difficult unsolved math conjecture (like Goldbach’s Conjecture) is true or false? Why or why not?

2. Suppose every time we invent a new kind of computer, we discover problems it cannot answer. Do you think human minds have similar built‑in limits, or can we always step outside them? What might that mean for whether we could ever completely understand our own thinking?

3. Knowing that some questions are undecidable, would you rather live in a world where every truth can eventually be computed, or a world where some truths will always require a creative leap? Which feels more exciting to you?