This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.
Announcements
The re-sit exam will be held in Room 021 on Monday 23/7, 10-12h.
Times and location
Class: Friday, 12-14, Room: Ludwigstr. 31, Room 021.
Exercise session: Wednesday, 11-12, Room: Ludwigstr. 28, Room 503.
Prerequisites
Basic knowledge of first-order logic.
Textbook
N. J. Cutland, Computability: an introduction to recursive function theory.
Course program (preliminary)
13-04 Introduction
Material: slides. Cutland, 1.1-1.2.
20-04 Unlimited register machines
Material: remainder of Chapter 1.
Exercises: 1(b,c,d,e) on pp. 21-22 + this exercise
27-04 Recursive functions
Material: Chapter 2 + 3.1-3.3
Exercises
04-05 Turing machines
Material: lecture notes
Exercises
11-05 Post systems
Material
Optional material 1; Optional material 2.
Exercises
18-05 The Church-Turing thesis, coding of programs
Material: slides + Sections 4.1-4.2
Practice exam. Example solutions.
25-05 Diagonalization, halting problem, s-m-n theorem, Kleene normal form
Material: Sections 4.3, 4.4, 5.1
Exercises
01-06 No class
08-06 Universal program, Reduction between problems, Rice’s theorem
Material: Sections 5.2, 5.3, 6.1
Exercises
15-06 Partial decidability
Material: Section 6.6
Exercises (for Wednesday 27/6)
29-06 Recursive and recursively enumerable sets
Material: Sections 7.1, 7.2
Exercises
06-07 Connections with arithmetics and Gödel’s theorem
Material: slides
13-07 Final exam