Are There Math Problems No Computer Can Ever Solve?
The dream of a perfect math machine
In 1928 the mathematician David Hilbert (1862–1943) asked a breathtaking question. Could someone invent a mechanical procedure—a set of clear, unbreakable rules—that would take any mathematical sentence, check it automatically, and announce “true” or “false”? If such a procedure existed, you could build a perfect math‑deciding machine. The problem was called the Entscheidungsproblem, the “decision problem.”
Many brilliant thinkers expected a yes. After all, mathematics seemed precise and rule‑governed. But only a few years later, a quiet logician named Alonzo Church (1903–1995) dropped a bombshell. He proved that no such machine could exist. Some questions, he showed, are forever beyond the reach of any step‑by‑step procedure—no matter how cleverly you program it.
Church’s proof rested on a careful definition of what it means to compute something. That definition became Church’s Thesis, one of the deepest ideas in logic and computer science. It links an intuitive notion—what we mean by “following an algorithm”—to exact mathematics, and it draws a permanent line around what computers can ever do.
What is an algorithm?
Before Church could prove that something is impossible, he had to say what counted as a computation. You follow an algorithm when you carry out a plan where each tiny step is completely determined. Think of a recipe that says “add 1, then multiply by 2, then write down the number.” There is no judgment call, no hunch—just blind obedience to the rules.
Church, like other logicians of his time, was hunting for a precise mathematical model of this idea. He called a function computable (or “effectively calculable”) if some algorithm can evaluate it for every input. For example, doubling a number is computable: you just follow the rule “multiply by two” and you always finish. But is every function computable?
For many everyday problems, yes. But Church suspected that some perfectly well‑defined questions cannot be answered by any algorithm. To say that clearly, he first had to build a formal system that captured what an algorithm can do.
Church drops a bombshell
Church invented a system called the lambda calculus, a tiny language that builds all its operations from rules about variables and substitution. Within that system he could define a large class of functions—the lambda‑definable functions. At the same time, other logicians (Gödel, Herbrand, Kleene) had defined a different collection called the recursive functions. Church proved that the two collections were exactly the same.
Then he made a daring philosophical leap. He proposed that every intuitively computable function is recursive (and therefore lambda‑definable). This claim, now called Church’s Thesis, is a bridge between our informal idea of an algorithm and the precise mathematical notion of recursiveness. It is not a theorem you can prove in the usual way—it is more like a hypothesis that captures what “computable” really means.
With this bridge in place, Church was able to show that a particular problem in elementary number theory cannot be solved by any algorithm. As a direct consequence, the Entscheidungsproblem has a negative answer: there is no mechanical test that can decide the truth of every statement of first‑order logic. The dream of a perfect math‑deciding machine was dead.
Turing’s better idea — the mental machine
Church’s proof was brilliant, but his lambda calculus was hard to grasp. Even he admitted that another thinker, Alan Turing (1912–1954), had found a better way to explain computation. Turing described a simple machine—now called a Turing machine—that reads and writes symbols on a paper tape according to a short list of rules. He argued that anything a human computer can do with pencil and paper, following a finite set of instructions, a Turing machine can do too.
This analysis was powerful because it didn’t just define computability; it showed why any plausible expansion of the idea would still land inside the same class of functions. Church himself said that Turing’s approach “has the advantage of making the identification with effectiveness evident immediately.” Ever since, the thesis is often called the Church‑Turing Thesis.
Turing’s model made it easier for everyone to see that functions like “determine halting” cannot be computed. The limit Church had discovered was not a trick—it was a real wall built into the very nature of step‑by‑step reasoning.
Why should we believe Church’s thesis?
Church’s thesis is a statement about all possible algorithms, not just the ones we’ve written down. How can you be confident that nothing has been left out? Logicians have gathered several strong reasons.
First, heuristic evidence. Huge families of functions that felt computable were found to be recursive. Nobody could cook up an example that was clearly computable by a human but lay outside the class.
Second, equivalence of diverse models. Lambda‑definability, recursiveness, Turing computability, and other formal definitions all ended up describing exactly the same set of functions. If your idea of computation was too narrow, it would be a miracle that so many very different approaches all landed in the same place.
Third, Turing’s direct analysis. Turing examined what a human must actually do when computing—looking at a limited number of symbols, moving step by step, relying on a finite stock of mental states—and argued that any such process can be simulated by his machine. For many logicians, this is the most compelling reason.
These strands of evidence do not amount to a mathematical proof, but they make Church’s Thesis one of the best‑supported conjectures in the whole of logic.
Why limits matter — checkable proofs and the logic we trust
Church cared deeply about more than just the boundaries of computation. He argued that any properly built logical language must be effective: its rules for forming sentences and checking proofs must be mechanically testable. Otherwise, when someone claims to have a proof, you could never be certain. A doubter might need a proof that the proof is a proof—and you’d spiral forever.
In a system that meets Church’s requirement, you can run a verification algorithm on any argument. If the algorithm says “yes, that’s a proof,” the argument is public and undeniable. This standard is what makes mathematics a cooperative enterprise. Even today, when computers check formal proofs, they rely on the kind of effective test Church demanded.
The unsolvability result also teaches us something humbling. No algorithm can decide all mathematical truths, and some problems—like the famous Halting Problem—are forever off‑limits to any program. That doesn’t mean we stop thinking. It means that human creativity and new ideas still have a place in mathematics. The limits Church uncovered are not a failure; they are a discovery about the shape of reason itself.
Think about it
- If a computer can never solve every math problem, what does that say about the human mind—do we have an ability that machines cannot copy?
- Can you describe a real‑life question that might be impossible for any step‑by‑step recipe to answer? What makes that question different?
- When you check a friend’s argument, do you follow a hidden algorithm in your head, or do you sometimes rely on a hunch? Why might that matter for being truly convinced?
