Rekursionstheorie
» This course is given in German.
Vorlesung im Sommersemester 2001
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V2 | Di 16:00 - 17:30 AH I | 24.04.2001 | Thomas |
| Ü1 | nach Vereinbarung 4116 | Thomas |
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.
Stichworte zum Inhalt:- Primitiv rekursive und allgemein rekursive Funktionen (die "erste funktionale Programmiersprache") als Basis für die Berechenbarkeit.
- Die Kernsätze: Universelle Programme, Rekursionssatz, Selbstreproduktion on Systemen, Kritik und Diskussion der Church-Turing These.
- Reduktionsbegriffe und die Struktur des Aufzählbaren (Vollständige Mengen, kreative Mengen, Posts Problem).
- Hierarchien des Unentscheidbaren: die arithmetische und die analytische Hierarchie.