Rekursionstheorie (Vorlesung)

Thema

Eine Einordnung der Rekursionstheorie (als Berechenbarkeitstheorie) in das Umfeld der Theoretischen Informatik finden Sie bei den „Lehrinformationen”.

Vorlesungsinhalt

Im Zentrum der Vorlesung stehen Berechenbarkeit, Aufzählbarkeit, Entscheidbarkeit, die das begriffliche Fundament der Informatik bilden.

Zunächst werden verschiedene Formen von Berechenbarkeit betrachtet, die im wesentlichen aus den Grundvorlesungen bekannt sind. Der Wert abstrakter Begriffe bei allgemeinen Untersuchungen wird verdeutlicht, zum Beispiel im Umfeld des Fixpunktsatzes.

Aufzählbarkeit und Entscheidbarkeit ergeben sich durch Abstraktion. Wir werden die Begriffe untersuchen und Eigenschaften kennenlernen, wir werden das Verhältnis der beiden Begriffe zueinander untersuchen, wir werden uns vor allem mit dem „am schwersten" Berechenbaren beschäftigen. Wir werden sehen, daß das Berechenbare bezüglich natürlicher Vergleichsbegriffe eine sehr komplexe Struktur erzeugt.

Zum Schluß der Vorlesung werden wir über das Berechenbare hinausgehen und uns mit Berechenbarkeit in „relativierten Welten" beschäftigen, also mit den Möglichkeiten, die „Welten" mit speziellem Allgemeinwissen bieten. Es wird sich eine Hierarchie des relativ Berechenbaren ergeben, die Arithmetische Hierarchie heißt.

Teilnahmevoraussetzungen

Alle verwendeten Begriffe werden definiert. Ein Verständnis für formale Methoden und abstrakte Probleme wird vorausgesetzt.