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