04-00-0167-vu Introduction to Computability Theory

Lehrende: Dr. rer. nat. Benjamin Seyfferth

Veranstaltungsart: Vorlesung und Übung

Orga-Einheit: FB04 Mathematik

Anzeige im Stundenplan: Einf. Berechbark.

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.

Voraussetzungen:
Einführung in die Mathematische Logik. Für Studierende der Informatik:
Formale Grundlagen der Informatik I.

Online-Angebote:
moodle