Seminar: Rekursionstheorie (S1G1)
Dozenten
- Prof. Dr. Peter Koepke
- Dr. Philipp Lücke
Termin
- Dienstags, 16:15 - 18:00 Uhr, Raum 1.007 im Mathematik-Zentrum.
- Begin: Dienstag, 08.04.2014.
Beschreibung
Die Rekursionstheorie untersucht die algorithmische Berechenbarkeit von Funktionen auf (abstrakten) Turingmaschinen oder Registermaschinen. Die Turing-Berechenbarkeit modelliert auf überzeugende Weise alle Funktionen, die in einem anschaulichen Sinn berechenbar sind. Andererseits erlaubt dieser Ansatz, exakt zu erfassen, dass gewisse Funktionen nicht berechenbar sind.
Wir folgen dem Lehrbuch "Computability" von Nigel Cutland, Cambridge 1997. Die Seminarvorträge entsprechen Abschnitten des Buches.
Nach der Einführung von Grundbegriffen wird die Äquivalenz verschiedener Berechenbarkeitsbegriffe gezeigt. Rechenbefehle und -programme können selbst Eingabe von Berechnungen sein. Insbesondere können berechenbare Funktionen auf ihr eigenes Programm angesetzt werden. Durch derartige Diagonalverfahren kann man Fragestellungen wie z.B. das "Halteproblem" definieren, deren Antwort nicht berechenbar ist. Die Gödelschen Unvollständigkeitssätze können in diesem Kontext bewiesen werden. Die Rekursionstheorie ist auch Basis der Komplexitätstheorie, die Klassifizierungen von Funktionen nach dem Grad ihrer Berechenbarkeitskomplexität untersucht.
Vorbesprechung
Montag, 03.02.2014, 17:15 Uhr, Raum 1.008 im Mathematik-Zentrum.
Vorträge
- Registermaschinen (Kapitel I): L. Timmerhaus.
- Berechenbare Funktionen (Kapitel II, erster Teil): R. Paßmann.
- Turing-Maschinen, Churchsche These (Kapitel II/III): T. Racs.
- s-m-n Theorem (Kapitel IV): K. Öcal.
- Universelle Programme (Kapitel V): F. Schächter.
- Entscheidbarkeit (Kapitel VI): M. Müllenbach.
- RE-Mengen und R-Mengen (Kapitel VII): A. Müller.
- Gödelscher Unvollständigkeitssatz (Kapitel VIII): T. Hamm.
- Theorie der Grade, relative Berechenbarkeit (Kapitel IX): M. Abdel-Rahmen.
- Komplexität (Kapitel XII): S. Wang.