The aim is to provide a basis for the understanding of some of the most fundamental concepts of theoretical computer science: the concept of an algorithm and models of algorithms, mechanizability, undecidability, and principal limits of mechanization of problems.

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.

ECTS breakdown

24 h: 5 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

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.