Logik in der Informatik Prof. Dr. Martin Grohe

Aktuelles

Einführung

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. Seitdem wurde Berechenbarkeitstheorie als Teildisziplin der mathematischen Logik weiterentwickelt, gleichzeitig bildet sie die Grundlage der theoretischen Informatik. Die eleganten Begriffe und Techniken der Berechenbarkeitstheorie dienen vor allem der Komplexitätstheorie oft als Vorbild.

Zur Illustration ein Beispiel: Ein Saboteur will durch einen Algorithmus jedes Programm P, etwa in der Programmiersprache JAVA, so ändern, dass das entstehende Programm P' etwas anderes leistet als P. Wie kann er das erreichen? - Gar nicht! Ein Hauptsatz der Berechenbarkeitstheorie besagt, dass der Saboteur sein Vorhaben nicht verwirklichen kann, egal welchen Sabotage-Algorithmus er benutzt.

Inhalt

Durch Anklicken der einzelnen Kapitel erhalten Sie das Skript zur Vorlesung.

Inhaltsverzeichnis und Notation
1. Berechenbare Funktionen und entscheidbare Prädikate
2. Numerierung berechenbarer Funktionen
3. Entscheidbare und rekursiv aufzählbare Mengen
4. Der Kleene'sche Fixpunktsatz
5. Die Struktur rekursiv aufzählbarer Mengen unter Many-One Reduktionen
6. Relative Berechenbarkeit und Turing Reduktionen
7. Die Struktur rekursiv aufzählbarer Mengen unter Turing Reduktionen
8. Die arithmetische Hierarchie
Literaturverzeichnis

Das ganze Skript in einen File erhalten sie hier.

Hier finden Sie einen Interpreter für die GOTO-Sprache und einige Beispielprogramme.

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungsbetrieb

Zeiten und Raum

Montags und Donnerstags 09-11 Uhr im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'306

 

Dozent

Prof. Dr. Martin Grohe

Sprechstunde in SS10: Donnerstags 11-12 Uhr

Übungen

Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.

Zeit und Raum

Donnerstags 11-13 Uhr im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'306

 

Übungsleiter

André Hernich

Übungsaufgaben

Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.

• Blatt 1 (15.4.2010; Abgabe am 22.4.2010)
• Blatt 2 (22.4.2010; Abgabe am 29.4.2010)
• Blatt 3 (29.4.2010; Abgabe am 6.5.2010)
• Blatt 4 (6.5.2010; Abgabe am 20.5.2010)
• Blatt 5 (20.5.2010; Abgabe am 27.5.2010)
• Blatt 6 (27.5.2010; Abgabe am 3.6.2010)
• Blatt 7 (3.6.2010; Abgabe am 10.6.2010)
• Blatt 8 (10.6.2010; Abgabe am 17.6.2010)
• Blatt 9 (24.6.2010; Abgabe am 1.7.2010)
• Blatt 10 (1.7.2010; Abgabe am 8.7.2010)

Prüfung

Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungsaufgaben erworben werden.

Literatur

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:

[BBJ]	G.S. Boolos, J.P. Burgess, and R.C. Jeffrey, Computability and Logic. 5. Auflage, Cambridge University Press, 2007.
[O]	P. Oddifreddi, Classical Recursion Theory, Volume I & II. North Holland, 1989 und 1999.
[R]	H. Rogers, Theory of Recursive Functions and Effective Computability. McGraw-Hill 1967.
[S]	R. Soare, Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Enumerable Sets. Springer Verlag, 1987.