Uni HH Logo

Berechenbarkeitstheorie
WS 2012/13
Universität Hamburg
Fachbereich Mathematik

LV-Nummer 65-???
Veranstalter: Prof. Dr. Benedikt Löwe, email: bloewe@science.uva.nl
Studentische Hilfskraft: Karl Heuer, e-mail: kmh@exmpl.de
Ort und Zeit: Dienstag 18-20 (Geom H6), Donnerstag 12-14 (Geom H3)
Übungen: Donnerstag 14-16 (Geom 241)
Inhalt:

Im Jahre 2012 jährt sich der Geburtstag von Alan Turing zum hundersten Male und Wissenschaftler aller Fachgebiete, die von Turings Werk berührt wurden, feiern dies im sogenannten Alan Turing Year / Turing-Jahr. Turing hat zahlreiche Bereiche der Mathematik und Informatik revolutioniert, von den Grundlagen der Logik bis zur Theorie der dynamischen Systeme in Biologie und Chemie.

Seine vielleicht berühmteste Leistung war die Entwicklung der Turing-Maschine, eines theoretischen und grundlegenden Modells der Berechenbarkeit, welches nicht nur der modernen Unterscheidung zwischen Hardware und Software zugrundeliegt, sondern auch genutzt werden kann, um Theoreme wie den Gödelschen Unvollständigkeitssatz und die Unentscheidbarkeit der Prädikatenlogik leicht zu beweisen.

In dieser Vorlesung erarbeiten wir die Grundlagen der Berechenbarkeitstheorie mit ihren Hauptanwendungen: dem Gödelschen Unvollständigkeitssatz und den Hierarchien der Unlösbarkeit von Problemen.

Ziel: Einführung in die Theorie der Berechenbarkeit; Beweis des Gödelschen Unvollständigkeitssatzes.
Für: Studierende der Mathematik und Informatik (und ggf. mathematisch begabte Studierende anderer Fächer mit Interesse an Grundlagen der Mathematik, Metamathematik und Informatik).
Vorkenntnisse: Spezifische Vorkenntnisse, insbesondere Vorkenntnisse in Logik, sind nicht nötig, aber nützlich. Mathematische Reife (d.h. Erfahrung mit dem Erarbeiten von mathematischen Beweisen anhand eines gegebenen Textes) wird vorausgesetzt.
Literatur: S. Barry Cooper, Computability Theory.
Übungen:
Bewertung: Am 31.1.2013 wird es eine Abschlußklausur geben, die die Grundlage für die Benotung bilden wird.
Last changed: 10 January 2013