Diese zweistündige Vorlesung soll in die klassische Rekursionstheorie, d.h. in die Theorie der berechenbaren Funktionen auf den natürlichen Zahlen, einführen. Die geplanten Themen sind: Berechenbarkeit, die Church'sche These, der s-m-n Satz der Satz von Trakhtenbrot, rekursive Aufzählbarkeit, Grade, Sprünge, Posts Problem, die finite injury priority und die infinite injury priority Techniken.

Literatur: Hartley Rogers Junior: Recursive Functions and Effective Computability, Piergiorgio Odifreddi: Classical Recursion Theory I, Robert Soare: Recursively Enumerable Sets and Degrees.