Rekursionstheorie
» Diese Veranstaltung wird auf deutsch gehalten.
» Es gibt einen L2P-Lernraum zu dieser Veranstaltung.
Vorlesung im Wintersemester 2008/2009
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V2 | Do 13:15-14:45, AH II | 16.10.2008 | Thomas |
| Ü1 | Di 13:15-14:00, AH I | 21.10.2008 | Thomas, Felscher |
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.
Vorwissen
Gute Kenntnisse in Berechenbarkeit und Komplexität aus den Grundveranstaltungen werden vorausgesetzt.
Credit Points
4 ECTS