Rekursionstheorie
Sommersemester 2021
Inhalt
Die Rekursionstheorie ist die Theorie des absolut Berechenbaren. Sie wurde durch Gödel, Church, Kleene, Turing und Post begründet und führt mit relativ kurzen Schlüssen zu weitreichenden Einsichten. Zur Illustration ein Beispiel:
Ein Saboteur will durch einen Algorithmus jedes C-Programm P so ändern, dass das entstehende Programm P' etwas anderes leistet als P. Wie kann er das erreichen? Ein Hauptsatz der Rekursionstheorie besagt, dass der Saboteur sein Vorhaben nicht verwirklichen kann, egal welchen Sabotage-Algorithmus er benutzt. Die eleganten Begriffe und Schlüsse der Rekursionstheorie haben für andere Disziplinen als Vorbild gedient, vor allem für die Komplexitätstheorie.
Wir geben eine Einführung in die elementaren Begriffe und Sachverhalte der Rekursionstheorie; historisch stellen sie eine wichtige Quelle für die Disziplin der Informatik dar.
Voraussetzungen
Diese Vorlesung ist ausschließlich an Master Studentinnen und Studenten gerichtet.
Grundvorlesung "Berechenbarkeit und Komplexität" wird vorausgesetzt.
Organisatorisches
Die Vorlesung wird auf Deutsch gehalten.
Termine
Diese 3-Stündige Vorlesung wird als 4-Stündige Veranstaltung gehalten. Sie findet jedoch nicht jede Woche statt.
Die genauen Termine werden noch bekannt gegeben.
Dozent
Übungsaufgaben
TBA
Prüfung
TBA