04-00-0167-vu Introduction to Computability Theory

Lehrende: Prof. Dr. phil. nat. Ulrich Kohlenbach

Veranstaltungsart: Vorlesung und Übung

Orga-Einheit: FB04 Mathematik

Anzeige im Stundenplan: Computability Theory

Fach:

Anrechenbar für:

Semesterwochenstunden: 3

Unterrichtssprache: Englisch

Min. | Max. Teilnehmerzahl: - | -

Lehrinhalte:
Diese Vorlesung gibt eine Einführung in die klassische Rekursionstheorie (Berechenbarkeitstheorie) und kulminiert in der Lösung von Posts Problem durch die Prioritätsmethode (Friedberg/Muchnik). Inhaltsverzeichnis: Basis- Maschine, Definition rekursiver Funktionen, Kodes und Indizes, Kleenes Normalform-Theorem, Kleenes Rekursionstheorem, These von Church, relative Rekursion, arithmetische Hierarchie, rekursiv aufzählbare Relationen, Turing-Grade, Lösung des Problems von Post, berechenbare Funktionale.

Literatur:
Shoenfield, Joseph R.: Recursion Theory. ASL and A K Peters, 96pp., 2001.
Cutland, Nigel J.: Computability. Cambridge University Press 1980.

Voraussetzungen:
empfohlen: Introduction to Computability Theory
Alternativ für Studierende der Informatik:
- Automaten, formale Sprachen und Entscheidbarkeit