|
Logik in der Informatik
Prof. Dr. Martin Grohe |
 Institut für Informatik |
Thema der Vorlesung ist die Theorie der berechenbaren Funktionen. Sie wurde durch Gödel, Church, Kleene, Turing und Post in den 30er Jahren des 20. Jahrhunderts begründet und bildet die fundamentale Grundlage der theoretischen Informatik. Die eleganten Begriffe und Techniken der Berechenbarkeitstheorie dienen für andere Teildisziplinen der Informatik, vor allem für die Komplexitätstheorie, als Vorbild. Oft führen in der Berechenbarkeitstheorie relativ kurze Schlüsse zu weitreichenden Einsichten.
Zur Illustration ein Beispiel: Ein Saboteur will durch einen Algorithmus jedes Java-Programm P so ändern, dass das entstehende Programm P' etwas anderes leistet als P. Wie kann er das erreichen? Ein Hauptsatz der Berechenbarkeitstheorie besagt, dass der Saboteur sein Vorhaben nicht verwirklichen kann, egal welchen Sabotage-Algorithmus er benutzt.
Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.
Zu Beginn der Semesterferien finden mündliche Prüfungen statt.
Die Vorlesung orientiert sich vor allem an folgendem Buch:
| [C] | N.J. Cutland, Computability. Cambridge University Press, 1980. |
Ergänzend seien auch folgende Bücher empfohlen:
| [H] | H. Hermes, Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Dritte Auflage, Springer Verlag, 1978. |
| [D] | M.D. Davis und E.J. Weyuker, Computability, Complexity, and Languages (Fundamentals of Theoretical Computer Science). Academic Press, 1983. |
| [O] | P. Oddifreddi, Classical Recursion Theory, Volume I & II. North Holland, 1989 und 1999. |
| [R] | H. Rogers, Theory of Recursive Functions and Effective Computability. |
| [S] | R. Soare, Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Enumerable Sets. Springer Verlag, 1987. |