decidability (under construction)
(2.9 hours to learn)
Summary
-No Summary-
Notes
This concept is still under construction.
Context
This concept has the prerequisites:
- Turing machines (Turing machines are the canonical model of computation when reasoning about decidability.)
- countable sets (A simple counting argument shows that not all languages are decidable.)
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.
Location:
Lecture "Decidability"
Other notes:
- Click on "Preview" to see the lecture videos.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Chapter 4, "Decidability," pages 165-182
Other notes:
- The material about regular and context-free languages is optional (and depends on earlier chapters).
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
- Section 8.1, "Problems that computers cannot solve," pages 315-324
- Section 9.1, "A language that is not recursively enumerable," pages 378-382
- Section 9.2, "An undecidable problem that is RE," pages 383-390
See also
-No Additional Notes-