Rekursionstheorie
Vorlesung im Wintersemester 2017/2018
Termine
Vorlesung
Di, 10:15 - 11:45 Uhr (5056)
Mi, 10:15 - 11:45 Uhr (5056
Übung
Do, 12:15 - 13:45 Uhr (5054)
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 in Deutsch gehalten.
Termine
Dienstag, 10:15 Uhr - 11:45 Uhr im 2356|056 (5056)
Mittwoch, 10:15 Uhr - 11:45 Uhr im 2356|055 (5056)
Diese 3-Stündige Vorlesung wird als 4-Stündige Veranstaltung gehalten. Sie findet jedoch nicht jede Woche statt.
Die genauen Termine werden in der ersten Vorlesung und im Campus-Office bekannt gegeben.
Dozent
Übungsaufgaben
TBA
Prüfung
TBA