This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.
Prerequisites
Basic knowledge of first-order logic.
Textbook
N. J. Cutland, Computability: an introduction to recursive function theory.
Course program
Class 1 - Course introduction
Material: slides
Class 2 - Unlimited register machines
Material: Cutland, Chapter 1
Class 3 - Recursive functions
Material: Cutland, Chapter 2 and Sections 3.1–3.2.
Class 4 - Turing machines
Material: lecture notes.
Class 5 - The Church-Turing thesis, coding of programs
Material: Cutland, Ch. 3.7, 4.1, 4.2; lecture notes
Class 6 - diagonalization, halting problem, s-m-n theorem
Material: remainder of Ch. 4, Ch. 6.1.1-6.1.3
Class 7 - Universal program, Kleene normal form
Material: Ch. 5, excluding section 2.2
Class 8 - Reduction between problems, Rice’s theorem
Material: Ch. 6, sections 1.4 – 1.7
Class 9 - Partial decidability
Material: Ch. 6, section 6 except for 6.8-6.10
Class 10 - More on partial decidability
Material: class notes + Ch. 7, sections 1 and 2 up to 2.6.
Class 11 - Recursive and recursively enumerable sets
Material: Ch. 7, section 2.7-2.9
Class 12 - Arithmetics and Gödel’s theorem
Material: slides