Introduction to Computability

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
Exercises: Section 3.3, ex. 1(b)-1(e);
write a URM program to decide the predicate “x divides y” (solution)

Class 3 - Recursive functions

Material: Cutland, Chapter 2 and Sections 3.1–3.2.
Exercises. Solutions.

Class 4 - Turing machines

Material: lecture notes.
Exercises. Solutions.

Class 5 - The Church-Turing thesis, coding of programs

Material: Cutland, Ch. 3.7, 4.1, 4.2; lecture notes
Exercises: Chapter 3, ex. 7.2.1 and 7.2.2; Chapter 4, ex. 2.3. Solutions.

Class 6 - diagonalization, halting problem, s-m-n theorem

Material: remainder of Ch. 4, Ch. 6.1.1-6.1.3
Exercises: Chapter 4, ex. 3.2 items 2 and 3,  4.4 item 2. Solutions.
Here is an exercise on undecidability and diagonalization. Solution.

1st Partial examSolutions

Class 7 - Universal program, Kleene normal form

Material: Ch. 5, excluding section 2.2
Exercises: Ch. 5 ex. 3.2.1 (solution), and here (discussed in class).

Class 8 - Reduction between problems, Rice’s theorem

Material: Ch. 6, sections 1.4 – 1.7
Exercises: Ch. 6, ex. 1.8.1 (b)-(i) (solutions)

Class 9 - Partial decidability

Material: Ch. 6, section 6 except for 6.8-6.10
Exercises: Ch. 6, ex. 6.14.4, and hereSolutions.

Class 10 - More on partial decidability

Material: class notes + Ch. 7, sections 1 and 2 up to 2.6.
ExercisesSolutions.

Class 11 - Recursive and recursively enumerable sets

Material: Ch. 7, section 2.7-2.9
Exercises: Ch. 7, ex. 2.18.(1,2,5,7). Solutions.

Class 12 - Arithmetics and Gödel’s theorem

Material: slides

2nd Partial exam - Solutions.