11.5 Undecidability Results
11.5 Undecidability Results The halting problem is the first major example of an undecidable problem. Once we know that one problem is undecidable, we can use it to prove that many other problems are undecidable too. A decision problem asks for a yes-or-no answer. In computability theory, we usually represent a decision problem as a language: $$ L \subseteq \Sigma^* $$ A machine decides $L$ if it always halts and...