The previous chapter ended by promising that the universal Turing machine would become the key tool for proving that certain problems can never be solved by any algorithm at all. This chapter delivers on that promise. It confronts one of the most profound results in all of computer science: there exist perfectly well-defined, easy-to-state problems that no computer, no matter how powerful, no matter how much time it is given, will ever be able to solve correctly for every possible input.
This might sound almost like a philosophical claim rather than a mathematical one, but it is provable with the same rigor as any theorem in this course. The proof rests on a clever technique called diagonalization, borrowed directly from a famous argument used decades earlier to show that some infinities are larger than others. Applying this same trick to Turing machines produces one of the most celebrated results in computability theory: the undecidability of the halting problem.
In this tutorial, you will learn the distinction between decidable and Turing-recognizable languages, the precise statement of the halting problem, a complete proof that the halting problem is undecidable, and how this single result can be extended to show that many other problems are undecidable as well, using a technique called reduction.
A language L is called decidable, sometimes also called recursive, if there exists a Turing machine that, for every possible input string, always eventually halts, correctly accepting every string that belongs to L and correctly rejecting every string that does not belong to L. The critical requirement here is that the machine must always halt, on every single input, without exception; a machine that sometimes runs forever without ever reaching a decision does not qualify.
Problem: Given a DFA and a string w, does the DFA accept w? This problem is decidable, since a simple algorithm exists: simulate the DFA on w, one symbol at a time, and after processing the entire string, check whether the final state is an accepting state. This simulation always finishes, since w has a finite length, and the algorithm always produces a definite yes or no answer.
Most of the questions studied earlier in this course, such as whether a given DFA accepts a given string, whether two regular expressions describe the same language, or whether a context-free grammar generates a particular string, turn out to be decidable, since reliable, always-halting algorithms exist to answer each of them.
A weaker notion than decidability is Turing-recognizability, sometimes called recursive enumerability. A language L is Turing-recognizable if there exists a Turing machine that halts and accepts every string belonging to L, but for strings that do not belong to L, the machine is allowed to either halt and reject, or simply run forever without ever halting at all.
Every decidable language is automatically Turing-recognizable, since a machine that always halts with a correct answer certainly satisfies this weaker requirement as well. The reverse, however, is not true. Some languages are Turing-recognizable without being decidable, meaning a machine exists that correctly identifies every string that does belong to the language, but that same machine might run forever on some string that does not belong to the language, never producing a definite rejection.
| Category | Requirement |
|---|---|
| Decidable | A Turing machine exists that always halts, correctly accepting or rejecting every possible input. |
| Turing-Recognizable but Not Decidable | A Turing machine exists that always halts and accepts every string in the language, but may run forever on some strings not in the language. |
| Not Turing-Recognizable | No Turing machine exists that can even reliably accept every string in the language. |
The halting problem asks a deceptively simple question: given the description of a Turing machine M and an input string w, does M eventually halt when run on w, or does it run forever? Formally, this is expressed as a language membership question.
HALT = { ⟨M, w⟩ | M is a Turing machine that halts when run on input w }
It would be enormously useful to have a general algorithm that could answer this question correctly for every possible machine M and every possible input w, essentially a universal debugging tool capable of predicting whether any given program will eventually finish or get stuck in an infinite loop. Alan Turing proved in his original 1936 paper that no such algorithm can possibly exist.
The proof proceeds by contradiction, using a diagonalization argument. Assume, for the sake of argument, that a Turing machine H exists that decides HALT, meaning H always halts and correctly determines, for any machine M and input w, whether M halts on w.
Assume H is a Turing machine such that: H(⟨M, w⟩) = accept, if M halts on w H(⟨M, w⟩) = reject, if M does not halt on w And H always halts on every input, since H is assumed to decide HALT.
Using H as a building block, construct a new machine D that takes the description of a single machine M as its input, and behaves as follows: D runs H on the input ⟨M, M⟩, checking whether M halts when given its own description as input. If H says M halts on M, then D deliberately enters an infinite loop. If H says M does not halt on M, then D immediately halts and accepts.
D(⟨M⟩):
Run H(⟨M, M⟩)
If H accepts (meaning M halts on M):
Loop forever
If H rejects (meaning M does not halt on M):
Halt and accept
This construction deliberately does the exact opposite of whatever H predicts, which is precisely the diagonalization trick at work here, mirroring the same kind of self-referential contradiction used in classic arguments about the sizes of infinite sets.
Now comes the critical, self-referential step: what happens when D is run on its own description, D(⟨D⟩)?
Case 1: Suppose D halts on input D. By definition of D, this only happens when H(⟨D, D⟩) rejects, meaning H predicted that D does NOT halt on D. But we assumed D does halt on D in this case, directly contradicting H's prediction. Case 2: Suppose D does not halt on input D (loops forever). By definition of D, this only happens when H(⟨D, D⟩) accepts, meaning H predicted that D DOES halt on D. But we assumed D does not halt on D in this case, again directly contradicting H's prediction.
Both possible cases lead to a direct contradiction with H's supposed correctness. Therefore, the machine H, assumed to decide HALT, cannot actually exist. Conclusion: HALT is undecidable. No Turing machine can correctly determine, for every possible machine M and input w, whether M halts on w.
This proof does not rely on any particular quirky machine or unusual input; it shows that the very existence of a hypothetical perfect halting-decider H leads to an unavoidable logical contradiction, no matter how H might be constructed internally. This is what makes the result so powerful: it rules out every conceivable algorithm for solving the halting problem, not just the ones anyone has actually tried.
It is worth noting that HALT, while undecidable, is still Turing-recognizable. A machine can simply simulate M running on w directly. If M eventually halts, the simulating machine also halts and accepts, correctly recognizing every pair where M does halt. The problem only arises when M does not halt on w, since the simulating machine, faithfully following M step by step, will then also run forever, never reaching a definite rejection. This exact asymmetry, being able to confirm a "yes" answer but never being able to confirm a "no" answer, is a hallmark of many undecidable-but-recognizable problems.
Once one problem is known to be undecidable, a powerful technique called reduction allows this single result to be leveraged into proving that many other problems are undecidable as well, without needing to repeat the full diagonalization argument each time. The basic idea is to show that if some new problem P were decidable, then HALT could also be decided by cleverly using a decider for P as a subroutine, which is already known to be impossible.
Consider the problem: given a Turing machine M, does M halt when started on a completely blank tape? This can be shown undecidable by reduction from HALT. Given any instance ⟨M, w⟩ of HALT, construct a new machine M' that first writes w onto an otherwise blank tape, then simulates M running on that tape. M' halts on a blank tape input if and only if M halts on w. If a decider existed for "does M halt on a blank tape," it could be used to decide HALT by first constructing M' and then checking whether M' halts on blank input, contradicting the proven undecidability of HALT.
This reduction technique is one of the most widely used tools in computability theory, allowing researchers to establish a growing catalog of undecidable problems by connecting each new problem back to a single, firmly established starting point, exactly as demonstrated with HALT above.
| Aspect | Decidable Problem | Undecidable Problem |
|---|---|---|
| Example | Does a given DFA accept a given string? | Does a given Turing machine halt on a given input? |
| Algorithm Guarantee | An algorithm exists that always halts with a correct yes or no answer. | No algorithm can exist that always halts with a correct answer for every input. |
| Practical Implication | The problem can be reliably automated and solved by software. | No software tool can ever fully and correctly automate this problem in general. |
The undecidability of the halting problem has real, practical consequences for software engineering, even outside pure theory. It explains, for instance, why no compiler or static analysis tool can ever be built that perfectly detects every possible infinite loop in arbitrary source code, no matter how sophisticated the tool becomes. Real-world tools work around this limitation by settling for incomplete but useful answers, either restricting themselves to a narrower, decidable subset of programs, or accepting that some cases will remain unresolved, reported as "unknown" rather than a definitive yes or no.
| Mistake | Correct Understanding |
|---|---|
| Assuming undecidable means "no algorithm has been found yet." | Undecidable means it has been mathematically proven that no algorithm can ever exist, not merely that one has not yet been discovered. |
| Confusing Turing-recognizable with decidable. | A Turing-recognizable language only guarantees halting and correct acceptance for strings in the language; decidability additionally requires halting and correct rejection for every string not in the language. |
| Believing the halting problem is undecidable only for unusual, contrived machines. | The proof shows that no algorithm can solve the halting problem in general, for any possible machine and input, not just specially constructed edge cases. |
| Thinking reduction proves a problem decidable. | Reduction from a known undecidable problem is used specifically to prove a new problem is also undecidable, not the other way around. |
Decidability and undecidability draw a sharp, mathematically proven boundary around what algorithms can and cannot ever achieve, no matter how much computing power or cleverness is applied. Through a careful diagonalization proof, this chapter demonstrated that the halting problem, one of the most natural questions imaginable about any given program, can never be solved by any general algorithm, and showed how this single result extends outward to many other undecidable problems through the reduction technique.
In this tutorial, you learned the distinction between decidable and Turing-recognizable languages, the precise statement of the halting problem, a complete diagonalization proof of its undecidability, and how reduction extends this result to other problems. With this foundation, you are ready to move on to the final chapter of this course, computational complexity, which shifts focus from what can be computed at all to how efficiently problems that are decidable can actually be solved.