Undecidable problem

• 1. Introduction

  ›

  An undecidable problem is a yes-or-no question that no computer program can ever answer correctly for every possible input. That claim sounds strange at first. We live in an age of fast processors and sophisticated software. Surely any well-posed question can be solved, given enough time and cleverness?

  In 1936, Alan Turing proved otherwise. He showed that there is a specific, concrete question about programs that no algorithm can reliably answer. That question is the halting problem: given any program and any input, does the program eventually stop, or does it run forever?

  The proof was not a statement about the limits of current technology. It was a proof that no such algorithm can exist, now or ever. And the halting problem turns out to be just one member of an enormous family. There are uncountably many undecidable problems. Any list of them, even an infinitely long one, is necessarily incomplete.

  Where do these problems come from, and what does it mean for mathematics itself that some questions resist all possible algorithms? The answers lead from a 1900 challenge by David Hilbert, through the paradoxes of logic, to a 2019 result about machine learning.

• 2. Defining the Problem

  ›

  A decision problem is a question that demands a yes or no answer for every input in some infinite set of inputs. "Is this number prime?" is a decision problem. "Is this string a valid word?" is a decision problem. The inputs can be numbers, strings, or more complex structures.

  Mathematicians formalize a decision problem as a set: the set of inputs for which the answer is yes. The problem "is the input even?" is formalized as the set of even numbers. A problem involving strings is converted into numbers through a technique called Gödel numbering, which assigns a unique natural number to every possible symbolic expression.

  A decision problem is called decidable if an algorithm exists that always produces the right answer in finite time. It is called undecidable if no such algorithm can be built. A third category sits between these two: partially decidable problems, where an algorithm exists that correctly returns yes when the answer is yes, but may run forever instead of returning no.

  The word "undecidable" itself carries two distinct meanings that can cause confusion. In one sense, borrowed from Gödel's work, a statement is undecidable if it can neither be proved nor refuted within a given formal system. In the other sense, from computability theory, a problem is undecidable if no computable function can answer every question it poses. The two senses are related: if a decision problem is undecidable in the computability sense, then no consistent formal system can systematically prove the answer to every instance of that problem.

• 3. Turing and the Halting Problem

  ›

  Alan Turing proved in 1936 that no general algorithm running on a Turing machine can solve the halting problem for all possible program-input pairs. The argument works by assuming such an algorithm exists and deriving a contradiction. If you could decide whether any program halts, you could construct a program that does the opposite of whatever the halting detector predicts about itself. That self-referential trap makes the assumption collapse.

  The result was later broadened by Rice's theorem, which extends the impossibility far beyond the halting question to a wide range of properties about program behavior.

  Turing's 1936 proof also forged a deep connection to Gödel's incompleteness theorems, announced just five years earlier. The proofs are structurally similar, and the concepts they raise are closely parallel. A weaker version of Gödel's First Incompleteness Theorem follows directly from the undecidability of the halting problem.

  That weaker form says that no effective axiomatization of natural number arithmetic can be both complete and sound, where "sound" means the system only proves statements that are actually true. Because soundness implies consistency, this weaker result is a consequence of Gödel's stronger statement. The philosophical weight here is significant. It means the limits on computation and the limits on formal proof are not separate phenomena. They are two faces of the same underlying mathematical boundary.

• 4. Hilbert's Challenge and Matiyasevich

  ›

  In 1900, David Hilbert posed a list of problems as a challenge to the coming century of mathematicians. His Tenth Problem asked for an algorithm that finds all solutions to any Diophantine equation, which is a polynomial equation with integer coefficients where only integer solutions are sought. Fermat's Last Theorem is a special case of this class of problem.

  The difficulty is that restricting solutions to integers changes everything. In the complex plane, a single equation in multiple variables typically has infinitely many solutions that are easy to find. Demand integer solutions, and the problem becomes a different beast entirely.

  In 1970, Russian mathematician Yuri Matiyasevich showed that Hilbert's Tenth Problem cannot be solved. He did this by mapping any Diophantine equation to a recursively enumerable set, then invoking Gödel's Incompleteness Theorem to show no algorithm can decide in general whether integer solutions exist.

  The word problem for groups had already fallen earlier. Max Dehn posed it in 1911: given a finitely presented group, is there an algorithm to determine whether two words in that group are equivalent? By 1955, the answer was established as no. The combined work of Gödel and Paul Cohen added further concrete examples. Gödel proved in 1940 that neither the continuum hypothesis nor the axiom of choice could be disproved in standard set theory. In the 1960s, Cohen proved that neither can be proved from those axioms either. These results stand independent of the incompleteness theorems.

• 5. Arithmetic That Defeats Itself

  ›

  The Peano axioms are the standard formal foundation for arithmetic, the rules from which most of elementary number theory is derived. A remarkable cluster of results shows that certain true statements about numbers simply cannot be proved within that system.

  In 1977, Paris and Harrington proved that the Paris-Harrington principle, a variant of the Ramsey theorem, is undecidable within the Peano axioms. The principle is true, and can be proved in the larger system of second-order arithmetic, but Peano arithmetic alone cannot reach it.

  Kruskal's tree theorem, which has direct applications in computer science, is undecidable from the Peano axioms as well, though it is provable in set theory. The undecidability of Kruskal's theorem holds even in a significantly stronger system built on the philosophy of mathematics called predicativism.

  Goodstein's theorem, a result about what Kirby and Paris identified as the Ramsey theory of natural numbers, is another statement Peano arithmetic cannot prove. Gregory Chaitin approached the boundary from a different direction entirely through algorithmic information theory. Chaitin proved that for any theory capable of representing enough arithmetic, there is an upper bound such that no specific number can be proved in that theory to have Kolmogorov complexity greater than that bound. Where Gödel's theorem is related to the liar paradox, Chaitin noted that his own result is connected to Berry's paradox.

  In 1973, Saharon Shelah showed that the Whitehead problem in group theory is undecidable in the first sense of that word, within standard set theory.

• 6. Undecidability Into the Present

  ›

  Undecidability did not stop being discovered after the foundational era. In 2007, researchers Kurtz and Simon proved that a natural generalization of the Collatz problem is undecidable. Their result built on earlier work by J.H. Conway from the 1970s. The Collatz problem itself asks whether repeatedly applying a simple rule to any positive integer always eventually reaches the number one. The generalization Kurtz and Simon studied takes that intuition further and falls beyond the reach of any algorithm.

  In 2019, Ben-David and colleagues constructed a learning model they named EMX and identified a family of functions whose learnability within that model is undecidable in standard set theory. This brought undecidability inside the theory of machine learning, showing that certain fundamental questions about what a model can learn are not merely hard but provably unanswerable by any algorithmic means.

  The range of these results spans logic, abstract machines, group theory, topology, number theory, and now learning theory. What connects them is the same underlying impossibility Turing identified in 1936: self-reference creates loops that no finite procedure can escape. The continuum hypothesis, which Gödel and Cohen together showed to be independent of ZFC set theory, remains one of the most famous open questions about what mathematical truth means when proof cannot reach it.