Kursinformation

Digitale Lehre
Diese Vorlesung gibt im ersten Teil eine Einführung in die klassische Rekursionstheorie (Berechenbarkeitstheorie) und kulminiert in der Lösung von Posts Problem durch die Prioritätsmethode (Friedberg/Muchnik): 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.
Im zweiten Teil behandeln wir die primitiv-rekursiven Funktionale endlichen Typs von Kleene und deren Erweiterung von Gödel, die S1-S9 berechenbaren Funktionale von Kleene, sowie die Kleene-Kreisel stetigen Funktionale

 

Lehrinhalte
Ausgewählte vertiefende Themen zur Logik.

Literatur
Literatur:
Shoenfield, Joseph R.: Recursion Theory. ASL and A K Peters, 96pp., 2001.
Longley, J., Normann, D., Higher-Order Computability. Springer 2015.

 

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

Online-Angebote
moodle

Digital Teaching
Course Contents:
This course gives in its first part a brief introduction to classical recursion (computability) theory culminating in the solution of Post’s problem by the priority method (Friedberg/Muchnik): the basic machine, definition of recursive functions, codes and indices, Kleene normal form theorem, Kleene recursion theorem, Church’s thesis, relative recursion, arithmetical hierarchy, recursively enumerable relations, Turing degrees, solution of Post’s problem, computable functionals.
In the 2nd part we discuss the primitive recursive functionals of Kleene and their extension by Gödel, the
S1-S9 computable functionals of Kleene and the Kleene-Kreisel continuous functionals.
 

Literature
depending on topic

Preconditions
Preconditions:
recommended: Introduction to Mathematical Logic
Alternatively: Logic as taught in CS programmes