An undecidable problem is a problem that no algorithm can solve correctly for every possible input. It’s not a matter of needing a faster computer or a cleverer programmer. The limitation is mathematical: for certain types of questions, a general-purpose solution provably cannot exist. This idea sits at the heart of computer science and defines the boundary of what computation can and cannot do.
Decidable vs. Undecidable
A problem is decidable if you can write a program that always finishes and gives the right yes-or-no answer, no matter what input you feed it. Checking whether a number is even, whether a word appears in a list, or whether a string of parentheses is balanced are all decidable. The program runs, it stops, and it’s correct every time.
An undecidable problem breaks that guarantee. No program exists that can take in every possible instance of the problem, always halt, and always produce the correct answer. You might be able to write a program that works for some inputs, or one that gives the right answer when it does stop, but you cannot build one that does both for all cases. NIST defines an undecidable problem as one “that cannot be solved for all cases by any algorithm whatsoever.”
There’s a useful middle category here called semi-decidable (sometimes called “recognizable”). For a semi-decidable problem, you can build a program that will correctly say “yes” whenever the answer is yes, but when the answer is “no,” the program might run forever without giving you an answer. It never lies to you, but it sometimes never finishes. Decidable problems are a strict subset of semi-decidable problems, and undecidable problems sit outside the decidable boundary entirely. Some undecidable problems aren’t even semi-decidable.
The Halting Problem: The Classic Example
The most famous undecidable problem is the halting problem: given a program and an input, will the program eventually stop running, or will it loop forever? Alan Turing proved in 1936 that no general algorithm can answer this question for every program-input pair.
The proof works by contradiction, and the core idea is elegant. Suppose you did have a magic subroutine that could look at any program and its input and correctly report “halts” or “loops forever.” You could then build a new program, call it Q, that does the following: given a program P as input, Q asks the magic subroutine whether P would halt if P were given itself as input. If the subroutine says “yes, it halts,” then Q deliberately enters an infinite loop. If the subroutine says “no, it loops forever,” then Q immediately halts.
Now ask: what happens when you run Q on itself? If Q halts on input Q, then by its own design it should have looped forever. If Q loops forever on input Q, then by its design it should have halted. Either way you get a contradiction. The only escape is that the magic subroutine cannot exist. No algorithm can solve the halting problem for all programs.
Rice’s Theorem: It Gets Worse
The halting problem might seem like one unfortunate edge case, but Rice’s theorem shows the situation is far more sweeping. It says that any “interesting” question about what a program computes is undecidable.
More precisely, pick any property that describes the behavior of a program (not how the code looks, but what it actually does). As long as that property is non-trivial, meaning at least one program has it and at least one program doesn’t, then no algorithm can look at an arbitrary program and correctly determine whether it has that property. Does a program accept every input? Undecidable. Does it produce the same output as some other specific program? Undecidable. Does it ever output the number 42? Undecidable. Rice’s theorem covers all of these at once.
Other Undecidable Problems
Many problems beyond the halting problem turn out to be undecidable. One well-known example is the Post Correspondence Problem. You’re given a set of domino-like tiles, each with a string on top and a string on the bottom. The question: can you arrange some sequence of these tiles (reusing tiles as many times as you want) so that the string formed by reading all the tops equals the string formed by reading all the bottoms? Despite how simple the setup sounds, no algorithm can answer this for every possible set of tiles.
The Busy Beaver problem offers another angle. It asks: among all possible programs of a given size that eventually halt, what’s the maximum number of steps any of them takes before halting? This function is perfectly well-defined for each program size, but it grows so fast that no computable function can keep up with it. You can compute the first few values by hand, but the function quickly becomes impossible for any algorithm to calculate.
Word problems in algebra, certain tiling questions in geometry, and equivalence questions about grammars in formal language theory are all undecidable as well. The landscape is broad.
Undecidable vs. Just Really Hard
It’s important not to confuse undecidable problems with problems that are merely difficult or slow to solve. NP-complete problems, like the traveling salesman problem, are famously hard. They appear to require time that grows exponentially with input size, and no one has found a fast shortcut. But they are decidable. Given enough time, a brute-force algorithm will check every possibility and give you the correct answer.
Undecidable problems are in a different category entirely. No amount of computational power fixes them. You could have a computer the size of the universe running until the heat death of everything, and it still could not solve the halting problem for all inputs. NP-complete problems represent practical barriers. Undecidable problems represent absolute, proven, permanent barriers.
Why This Matters for Real Software
Undecidability isn’t just a theoretical curiosity. It has direct consequences for the tools programmers use every day. Compilers and code analysis tools would love to answer questions like: will this program ever crash? Could this variable point to the same memory location as that one? Will this loop always terminate?
These are all undecidable in their general form. A foundational result in programming language research showed that “may alias” analysis (determining whether two references could ever point to the same data) is undecidable, and “must alias” analysis (determining whether they always do) is even harder, not even semi-decidable. This holds for any language with conditionals, loops, and dynamic memory, which is essentially every mainstream programming language.
The practical response is approximation. Static analysis tools use simplifying assumptions and conservative estimates. A compiler might warn you about a potential infinite loop even when the loop would actually terminate, because it cannot know for certain. A security scanner might flag code as potentially vulnerable when it’s actually safe. These tools are genuinely useful, but undecidability guarantees they will always have blind spots or false alarms. Perfect, fully automatic analysis of arbitrary programs is not a goal anyone is failing to reach. It’s a goal that provably cannot be reached.
How Undecidability Is Proven
Most undecidability proofs work through a technique called reduction. You take a problem already known to be undecidable (usually the halting problem) and show that if you could solve your new problem, you could use that solution to solve the halting problem too. Since the halting problem is unsolvable, your new problem must be unsolvable as well.
This is how the Post Correspondence Problem was proven undecidable: by constructing a set of tiles that, for any given program and input, has a matching sequence if and only if that program halts on that input. If you could solve the tile-matching problem, you’d have a backdoor to solving the halting problem. Since no such backdoor can exist, the tile-matching problem is undecidable.
The same reduction strategy extends through a long chain. Each new undecidable problem becomes a potential starting point for proving the next one. This is why the catalog of known undecidable problems is so large: once you have one, you can propagate the impossibility to any problem powerful enough to encode it.