Rekursionstheorie

 

Sommersemester 2021

 
endloser Spiegel Urheberrecht: © M. Grohe

Ansprechpartner

Name

Jan Böker

Telefon

work
+49 241 80 21723

E-Mail

E-Mail
 

Termine

Vorlesung
Montags 10:30 -12:00
Donnerstags 10:30 -12:00

Übung
tba

 
 
Vorlesungsvorstellung
 

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

Martin Grohe

 

Übungsaufgaben

TBA

Prüfung

TBA