Lehrende: Prof. Dr. phil. nat. Ulrich Kohlenbach; Dr. rer. nat. Nicholas Norbert Pischke
Veranstaltungsart: Vorlesung und Übung
Orga-Einheit: FB04 Mathematik
Anzeige im Stundenplan: 04-10-0600
Fach:
Anrechenbar für:
Semesterwochenstunden: 6
Unterrichtssprache: Englisch
Min. | Max. Teilnehmerzahl: - | -
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
Selected Topics in Logic: Computability Theory Exercise
Prof. Dr. phil. nat. Ulrich Kohlenbach; Dr. rer. nat. Nicholas Norbert Pischke
Do, 25. Apr. 2024 [11:40]-Do, 18. Jul. 2024 [13:20]