Computability
Summary
Very nice course! Here are the notes (handwritten).
Coverage
- Turing Machines (standard, with/without final state(s), multitape, multitrack, single-way, multiway) and their equivalences.
- Nondeterministic Turing Machines and their equivalence with standard Turing Machines (see also image).
- Recognizing/deciding a language
- Macros
- Turing-computable number-theoretic functions,
- Primitive recursive functions, bounded minimization
Mu recursion is somehow not included in this summary.