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.
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
P. Odifreddi, Classical Recursion Theory, Studies in Logic, North Holland 1989