Selecta Mathematica II

Turing-Maschinen und berechenbare Funktionen I: Präzisierung von Algorithmen.- § 1. Naive Vorbetrachtungen.- 1. Algorithmen in der Mathematik. Geschichtliches.- 2. Unmöglichkeitsbeweise. Churchsche These.- 3. Alphabete und Wortmengen.- 4. Eine intuitive Analyse des Algorithmenbegriffs.- 5. Berechenbare Funktionen.- 6. Entscheidbarkeit.- § 2. Motivierung und Definition von Turing-Maschinen.- 1. Intuitive Normierung von Algorithmen.- 2. Turing-Maschinen.- 3. Turing-berechenbare Funktionen.- Turing-Maschinen und berechenbare Funktionen II.- § 3. Beispiele für Turing-Maschinen. Turing-Diagramme.- 1. Die Elementarmaschinen.- 2. Weitere Maschinen.- 3. Motivationen für Turing-Diagramme.- 4. Definition der Turing-Diagramme.- 5. Erklärung der Arbeitsweise einer durch ein Diagramm gegebenen Maschine T.- 6. Beispiele für Turing-Diagramme. Weitere Vereinfachungen.- 7. Konstruktion von Tafeln aus Diagrammen.- 8. Weitere Beispiele von Turing-Maschinen.- 9. Nachweis der Turing-Berechenbarkeit einiger spezieller Funktionen.- 10. Darstellung einer Turing-Maschine durch ein aus den Elementarmaschinen zusammengesetztes Diagramm.- § 4. Normierte Turing-Berechenbarkeit.- 1. Die Maschine T§.- 2. Simulierung über dem Alphabet {|}.- 3. Normierte Turing-Berechnung.- 4. Eine Verschlüsselmaschine für n-Tupel.- 5. Eine Entschlüsselmaschine.- 6. Einsetzung Turing-berechenbarer Funktionen.- § 5. Einfache Beispiele unentscheidbarer Mengen.- 1. Maschinenwörter.- 2. Eine unentscheidbare Menge.- 3. Weitere unentscheidbare Mengen.- Turing-Maschinen und berechenbare Funktionen III.- § 6. Eine universelle Turing-Maschine und das Aufzählungstheorem von Kleene.- 1. Die universelle Turing-Maschine U.- 2. Das Kleenesche Aufzählungstheorem für Turingberechenbare Funktionen.- 3. Das Halteproblem für U.- Literatur I–III.- Aufzählbarkeit.- §1. Einleitung.- 1. Der intuitive Begriff der Aufzählbarkeit. Inhaltsübersicht.- 2. Historische Bemerkungen.- § 2. Naive Sätze über aufzählbare Mengen.- 1. Vorbemerkungen.- 2. Die Zurückführung des Berechenbarkeitsbegriffs auf den Aufzählbarkeitsbegriff.- 3. Die Zurückführung des Aufzählbarkeitsbegriffs auf den Berechenbarkeitsbegriff.- 4. Aufzählbarkeit und Entscheidbarkeit.- § 3. Turing-Aufzählbarkeit.- 1. Definition und Charakterisierungen Turing-aufzählbarer Mengen.- 2. Abgeschlossenheitseigenschaften Turing-aufzählbarer Mengen.- 3. Das Aufzählungstheorem.- 4. Nicht Turing-aufzählbare Mengen.- §4. Smullyan-Aufzählbarkeit.- 1. Erzeugung von Mengen durch Kalküle.- 2. Smullyansche formale Systeme.- 3. Reduktion auf Wortmengen.- 4. Spezielle Smullyan-Systeme.- § 5. Smullyan- und Turing-Aufzählbarkeit.- 1. Die Smullyan-Aufzählbarkeit der Turing-aufzählbaren Mengen.- 2. Die Turing-Aufzählbarkeit der Smullyan-aufzählbaren Mengen.- 3. Ein unentscheidbares Smullyan-System.- 4. Abschließende Bemerkungen.- § 6. Die Nichtaufzählbarkeit der wahren arithmetischen Aussagen und die Unentscheidbarkeit der Arithmetik.- 1. Arithmetische Ausdrücke und Aussagen.- 2. Deutungen. Arithmetische Prädikate.- 3. Eine Übersicht.- 4. Einfache arithmetische Relationen und Paarfunktionen.- 5. Verschlüsselung von endlichen Folgen natürlicher Zahlen.- 6. Die Arithmetisierung von ?.- 7. Anhang. Das Gödel-Prädikat. Das Schema F*(?l, ?2, ?3)..- 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.- Literatur.- 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.- Literatur.- Namenverzeichnis.- Symbolverzeichnis.