decidability (under construction)

(2.9 hours to learn)


-No Summary-


This concept is still under construction.


This concept has the prerequisites:


  • Define the sets of decidable and recursively enumerable languages.
  • Be able to show that some simple languages are decidable.
  • Prove, using a counting argument, that not all languages are decidable.
  • Prove that the halting problem is undecidable.
  • Prove that the universal language is recursively enumerable.

Core resources (read/watch one of the following)


Coursera: Automata
An introductory course on automata and the theory of computation.
Author: Jeffrey D. Ullman
Other notes:
  • Click on "Preview" to see the lecture videos.


See also

-No Additional Notes-