Berechenbarkeit, Unbeweisbarkeit und das Unendliche

Dozent:innen: Dr. rer. nat. Markus Blumenstock
Kurzname: 08.079.4431
Kurs-Nr.: 08.079.4431
Kurstyp: Vorlesung/Übung

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. Zumindest muss man wissen, was Turingmaschinen und abzählbare Mengen sind.

Digitale Lehre

Es wird Moodle verwendet.

Empfohlene Literatur

Robert I. Soare. Turing Computability
Dirk W. Hoffmann. Grenzen der Mathematik

Es gibt ein LaTeX-Skript mit allen behandelten Inhalten.

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 Kolmogorow-Komplexität und primitiv-rekursive Funktionen behandelt. Der Berechenbarkeitsanteil macht ca. 60 % aus, der über Unbeweisbarkeit und Ordinalzahlen ca. 40 %.

Termine

Datum (Wochentag) Zeit Ort
14.04.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
21.04.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
28.04.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
05.05.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
12.05.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
19.05.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
26.05.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
02.06.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
09.06.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
16.06.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
23.06.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
30.06.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik
07.07.2026 (Dienstag) 12:15 - 13:45 04 432
2413 - Neubau Physik/Mathematik