decidability (under construction)

(2.9 hours to learn)

Summary

-No Summary-

Notes

This concept is still under construction.

Context

This concept has the prerequisites:

Goals

  • 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)

-Free-

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.

-Paid-

See also

-No Additional Notes-