This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.

---

Times and location

Class: Wednesday, 12-14. Ludwigstr. 31, Room 021.
Exercise session: Thursday, 14-15. Ludwigstr. 28, Room 503.

---

Prerequisites

Basic knowledge of first-order logic.

---

Assessment

Final exam: 24-07.
Time and place: 12-14, room 021

Re-sit exam on 02-08.
Time and place. 10-12, room 021

---

Textbook

N. J. Cutland, Computability: an introduction to recursive function theory.

---

Course program (preliminary)

24-04 Introduction
Material: Slides, Ch. 1.1-1.3 of the book.
Exercises: 1(a,b,c,d) on pp. 21-22 + this exercise

---

Part I: models of computation

08-05 Unlimited register machines
Material: Ch. 1.4-1.5.
Exercises for 16-05.

15-05 Recursive functions
Material: Ch. 2 and 3.2.
Exercises for 23-05.

22-05 Turing machines
Lecture notes.
Exercises for 06-06.

29-05 Post systems
Material: Minsky Ch 12. Optional: Minsky Ch 13.
Exercises for 13-06.

05-06 The Church-Turing thesis, coding of programs
Material: Slides on CTT.

---

Part II: introduction to computability theory

12-06 Coding, diagonalization, halting problem.
Material: Lecture notes on coding, Chapter 4.1-4.3

19-06 s-m-n theorem, universal programs.
Material: Chapter 4.4, 5.1, 5.3
Exercises for 27-06. Example solutions.

26-06 Kleene normal form, reduction between problems, Rice’s theorem
Material: Chapter 6.1
Exercises for 04-07.

03-07 Partial decidability.
Material: Chapter 6.6
Exercises for 11-07.

10-07 Recursive and recursively enumerable sets
Material: Chapter 7.1, 7.2
Exercises for 18-07.

17-07 Connections with arithmetic and Gödel’s theorem
Slides

24-07 Final exam

---

For the followers of Operation Arturo:
picture  another picture