โ Theory of Computation learning pathTheory of Computation ยท Module 9 of 10
Decidability
Problems no algorithm can solve.
๐ Key ideas
- A problem is decidable if some TM always halts with the right yes/no answer.
- The halting problem (does program P halt on input x?) is undecidable, proved by diagonalisation.
- Reductions show a new problem is undecidable by reducing a known undecidable problem to it.
- Rice's theorem: every non-trivial property of the language of a TM is undecidable.
- Post Correspondence Problem is another classic undecidable problem.
๐ก Real-life example: The halting problem is like asking for a perfect tester that predicts whether any app will ever freeze; no such tester can exist for all apps.
Decidable problemSolvable by a TM that always halts
Halting problemWhether a program halts on an input
ReductionTransforming one problem into another
Rice's theoremNon-trivial semantic properties of TMs are undecidable