Decidability and Undecidability
A language is decidable (recursive) if some TM halts on every input and accepts exactly the strings in the language. It is undecidable if no such TM exists.
Theory of Computation · topic
Decidability and undecidability
Halting and acceptance problems, diagonalisation, mapping reductions and their direction, Rice's theorem and when it does not apply, Post correspondence, the decidability master table for regular, DCFL, CFL, CSL, recursive and RE languages, and complements of REC and RE.
Study this topic
Decidability and undecidability cheat sheets
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.