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.
Basic knowledge of first-order logic.
Final exam: 24-07.
Time and place: 12-14, room 021
Re-sit exam on 02-08.
Time and place. 10-12, room 021
N. J. Cutland, Computability: an introduction to recursive function theory.
Course program (preliminary)
Part I: models of computation
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
26-06 Kleene normal form, reduction between problems, Rice’s theorem
Material: Chapter 6.1
Exercises for 04-07.
17-07 Connections with arithmetic and Gödel’s theorem