Selecta Mathematica II

Inhaltsverzeichnis

• Turing-Maschinen und berechenbare Funktionen I: Präzisierung von Algorithmen.
• § 1. Naive Vorbetrachtungen.
• § 2. Motivierung und Definition von Turing-Maschinen.
• Turing-Maschinen und berechenbare Funktionen II.
• § 3. Beispiele für Turing-Maschinen. Turing-Diagramme.
• § 4. Normierte Turing-Berechenbarkeit.
• § 5. Einfache Beispiele unentscheidbarer Mengen.
• Turing-Maschinen und berechenbare Funktionen III.
• § 6. Eine universelle Turing-Maschine und das Aufzählungstheorem von Kleene.
• Literatur I–III.
• Aufzählbarkeit.
• §1. Einleitung.
• § 2. Naive Sätze über aufzählbare Mengen.
• § 3. Turing-Aufzählbarkeit.
• §4. Smullyan-Aufzählbarkeit.
• § 5. Smullyan- und Turing-Aufzählbarkeit.
• § 6. Die Nichtaufzählbarkeit der wahren arithmetischen Aussagen und die Unentscheidbarkeit der Arithmetik.
• Literatur.
• Entscheidungsproblem und Dominospiele.
• § 1. Zum Entscheidungsproblem der Prädikatenlogik. Teil 1..
• § 2. Ausdrücke, Präfixe, Präfixtypen. Durch solche Typen bestimmte Ausdrucksklassen.
• § 3. Erfüllbarkeit von Ausdrücken.
• § 4. Zum Entscheidungsproblem der Prädikatenlogik. Teil 2..
• § 5. Dominoprobleme.
• § 6. Die Definition des einer Turing-Tafel zugeordneten Eck-Dominospiels $${D_{{T^{,\;}}}}D_T^0$$.
• § 7. Lemma: Wenn M(T) angesetzt auf das leere Band, unendlich lange läuft, ist das Eck-Dominospiel $${D_{{T^{,\;}}}}D_T^0$$ gut.
• § 8. Lemma: Wenn das Eck-Dominospiel $${D_{{T^{,\;}}}}D_T^0$$ gut ist, läuft M(T), angesetzt auf das leere Band, unendlich lange.
• § 9. Die Definition des einem Eck-Dominospiel $$D,\;{D^0}$$ zugeordneten Ausdrucks $${\alpha _{D,\;{D^0}}}$$.
• § 10. Lemma: Wenn das Eck-Dominospiel $$D,\;{D^0}$$ gut ist, dann ist $${\alpha _{D,\;{D^0}}}$$ erfüllbar.
• § 11. Lemma: Das Eck-Dominospiel $$D,\;{D^0}$$ ist gut, wenn$${\alpha _{D,\;{D^0}}}$$ erfüllbar ist.
• § 12. Übergang zur engeren Prädikatenlogik.
• § 13. Ausblick auf die Ausdrucksklasse ? ? ? und das Diagonal-Dominoproblem.
• Turing-Maschinen und zufällige 0–1-Folgen.
• § 1. Die Kolmogorovsche Komplexität endlicher 0–1-Wörter.
• § 2. Ein gescheiterter Versuch.
• § 3. Der Raum der unendlichen 0–1-Folgen.
• § 4. Zufällige unendliche 0–1-Folgen.
• Namenverzeichnis.
• Symbolverzeichnis.