โ† Theory of Computation learning path
Theory of Computation ยท Module 9 of 10

Decidability

Problems no algorithm can solve.

๐Ÿ“– Key ideas

  1. A problem is decidable if some TM always halts with the right yes/no answer.
  2. The halting problem (does program P halt on input x?) is undecidable, proved by diagonalisation.
  3. Reductions show a new problem is undecidable by reducing a known undecidable problem to it.
  4. Rice's theorem: every non-trivial property of the language of a TM is undecidable.
  5. 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