Rekursionstheorie

 

Vorlesung im Wintersemester 2017/2018

 

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

Martin Grohe

 

Übungsaufgaben

TBA

Prüfung

TBA