Computability
A 17-module path through computability, in study order from foundations to the frontier.
Modules
- The Turing Machine Model
- Configurations and Computation of Turing Machines
- Decidable and Turing-Recognizable Languages
- Multitape Turing Machines
- Nondeterministic Turing Machines
- The Church-Turing Thesis
- Encodings and Enumerators
- The Universal Turing Machine
- Decidable Problems About Automata
- Diagonalization and the Countability of Machines
- The Halting Problem and A_TM
- Undecidability by Diagonalization
- Closure Properties and the Co-Turing-Recognizable Class
- Mapping Reducibility
- Rice's Theorem
- The Recursion Theorem
- Oracles and the Arithmetic Hierarchy