After successful completion of the course, students are able to independently prove various advanced  computability-theoretic statements and facts, and to apply results presented in the lectures to achieve this.

Introduction to computability theory: unsolvable problems, models of computations (Turing machines, register machines, recursive functions, lambda calculus), Church-Turing thesis, numbering of computable functions, numbering programs, the diagonal method, the s-m-n theorem, universal programs, Kleene's theorem, recursive and recursively enumerable sets, Rice's theorem. The LOOP-hierarchy and enumerations of subrecursive classes. Didactic procedure: During the course two sheets of exercises will be distributed which have to be solved by the students on their own.

Lecture

ECTS breakdown

24 h: 6-8 lectures

16 h: solving 2 sheets of ex. a 7 ex.

4 h: typing solutions in LaTeX

30 h: preparation for final examination

1 h: final examination

-----------------------------------------

75 h = 3 ECTS

2 sets of exercises and an oral exam

P. Odifreddi, Classical Recursion Theory, Studies in Logic, North Holland 1989

Some basic knowledge in mathematical logic and theoretical computer science is required; in particular knowledge in first-order predicate logic is of major importance.