Introduction to Computability Theory

Diese Vorlesung gibt eine Einführung in die klassische Rekursionstheorie (Berechenbarkeitstheorie) und kulminiert in der Lösung von Posts Problem durch die Prioritätsmethode (Friedberg/Muchnik). Inhaltsverzeichnis: Basis- Maschine, Definition rekursiver Funktionen, Kodes und Indizes, Kleenes Normalform-Theorem, Kleenes Rekursionstheorem, These von Church, relative Rekursion, arithmetische Hierarchie, rekursiv aufzählbare Relationen, Turing-Grade, Lösung des Problems von Post, berechenbare Funktionale.