Lehrende/r: Dr. rer. nat. Markus Blumenstock
Veranstaltungsart: Vorlesung/Übung
Anzeige im Stundenplan: 08.079.4431
Semesterwochenstunden: 4
Credits: 6,0
Unterrichtssprache: Deutsch
Min. | Max. Teilnehmerzahl: - | -
Voraussetzungen / Organisatorisches: Vorkenntnisse in Mathematik und theoretischer Informatik werden stark empfohlen. Besonders die Veranstaltungen "Diskrete Mathematik für Informatiker" und "Formale Sprachen und Berechenbarkeit" sollten gehört worden sein.
Inhalt: - Isomorphiesatz von Myhill - Rekursionssatz von Kleene - Konstruktion einer einfachen Menge nach Post - Axiomatische Mengenlehre - Gödels Unvollständigkeitssatz und Rossers Trick vom berechenbarkeitstheoretischen Standpunkt - Ordinalzahlen - Satz von Goodstein und die Kirby-Paris-Hydra Wenn die Zeit reicht, werden weitere Themen wie z. B. Kolmogorow-Komplexität behandelt. Der Berechenbarkeitsanteil macht ca. 60 % aus, der über Unbeweisbarkeit und Ordinalzahlen ca. 40 %.
Empfohlene Literatur: Robert I. Soare. Turing Computability Dirk W. Hoffmann. Grenzen der Mathematik
Digitale Lehre: Es wird LMS verwendet, das Skript ist in Overleaf verfügbar.
