Instituts-Logo Logik in der Informatik
Prof. Dr. Martin Grohe
Humboldt-Logo

Proseminar Grenzen der Berechenbarkeit

Aktuelles Einführung Zeit und Raum Literatur Vorträge

Aktuelles

Die abschließende Sitzung des Proseminars fand am Dienstag, dem 16. Juni statt.


Einführung

Zentrale Ergebnisse der Logik sind Vollständigkeitssätze, die im Prinzip besagen, dass sich das logische Folgern "mechanisch" in gewissen Beweiskalkülen nachvollziehen lässt. Allerdings stößt man mit solchen mechanischen Verfahren zum logischen Schließen schnell an prinzipielle Grenzen. Das wird etwa deutlich in der "Unentscheidbarkeit der Logik der ersten Stufe", welche besagt, dass es keinen Algorithmus gibt, der entscheidet, ob ein gegebener Satz der Logik der ersten Stufe erfüllbar ist.

Diese Grenzen der formalen Methode werden wir in diesem Proseminar genauer untersuchen, von grundlegenden Fragen der Berechenbarkeitstheorie wollen wir uns dabei bis zu den Gödelschen Unvollständigkeitssätzen vorarbeiten.

Das Proseminar schließt sich in an die Vorlesung "Theoretische Informatik I" an, vorausgesetzt werden deshalb gute Kenntnisse des in dieser Vorlesung behandelten Stoffes.


Zeit und Raum

Dienstag 15 - 17 Uhr im Erwin Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'304


Literatur

Alle Vorträge kommen aus folgendem Buch:
[S] R. M. Smullyan, Gödel's Incompleteness Theorems.
Ergänzend sei auch noch auf die folgenden Bücher verwiesen:
[EFT] H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die Mathematische Logik.
[BBJ] G. S. Boolos, J. P. Burgess, R. C. Jeffrey, Computability and Logic.
[F] T. Franzen, Gödel's Theorem.
[NN] E. Nagel, J. R. Newman, Gödel's Proof.
[S2] R. M. Smullyan, To Mock a Mockingbird - and Other Logic Puzzles.


Vorträge

Vortrag 0
[S] Kap. I.
28.4.2009 Bastian Laubner
Folien
Vortrag 1
[S] Kap. II, §3-5 (S.19-24).
5.5.2009 Anja Kunkel
Folien
Vortrag 2
[S] Kap. II, §6 (S.24-27).
19.5.2009 Daniel Miehe
Folien
Vortrag 3
[S] Kap. III, §1 und §2 (S.28-33).
26.5.2009 Daniel Lunow
Folien
Vortrag 4
[S] Kap. III, §3 und §4 (S.33-37 oben).
2.6.2009 Daniel Miehe
Folien
Vortrag 5
[S] Kap. IV, §1-3 (S.40-45).
9.6.2009 Daniel Lunow
Folien
Vortrag 6
[S] Kap. IV, §4-6 (S.45-50).
16.6.2009 Anja Kunkel
Folien

Last modified: Wed Apr 15 15:50:47 CEST 2009
Martin Grohe
Valid HTML 4.01!