3-4 hours of lectures per week.
Lecturer
Ulrich Kohlenbach
Content
The course gives an introduction to computability theory including topics like: subrecursive functions, recursive functions and relations, codes and indices, S-m-n theorem, recursion theorems, normal forms, word problems, undecidable theories, degrees of unsolvability, arithmetical and analytical hierarchy.We will also briefly treat computability in function arguments (so-called type-2 computability).This will allow to finish the course with a brief introduction to computability on real numbers and other continuous data types.
Prerequisites
Models and logic (dModLog) (very useful but not strictly necessary).
Literature
J.R. Shoen eld: Recursion Theory. A.K. Peters, Wellesley 2001 (Reprint of Lecture Notes in Logic 1, Springer-Verlag 1993). In addition, two handouts on computability on real numbers and subrecursive functions will be used.