Die Berechenbarkeitstheorie (oder Rekursionstheorie) ist ein Grenzgebiet zwischen Mathematischer Logik und Theoretischer Informatik. Sie behandelt Formalisierungen des intuitiven Berechnungsbegriffs. Die Methoden der Berechenbarkeitstheorie sind in vielen Bereichen der Mathematischen Logik und der Theoretischen Informatik wichtig und bilden auch ein Fundament für den Beweis des Gödelschen Unvollständigkeitssatzes. Die Techniken, die in dieser Vorlesung behandelt werden, sind daher für Mathematiker, Informatiker, Linguisten und Philosophen gleichermaßen bedeutend.
Die Vorlesung richtet sich an Mathematiker, Informatiker, Linguisten und Philosophen. Sie setzt keinerlei Vorkenntnisse in Logik voraus, aber eine gewisse Erfahrung im Umgang mit formalen Konzepten.
Ein Leistungsnachweis wird für regelmäßige Teilnahme an den Übungen und das schriftliche Bearbeiten einer hinreichend großen Zahl der Übungsaufgaben vergeben.
In dieser Vorlesung werden wir zunächst die Begriffe der Turingmaschine und der Registermaschine kennenlernen, dann die Standardtheorie der Berechenbarkeit kennenlernen. Der Kurs orientiert sich zum Teil am Buch von Shoenfield, Recursion Theory.
Literatur: (DVI-File) (PS-File) (PDF-File)Last changed: July 11th, 2002