Selecta Mathematica II

This item is printed on demand - it takes 3-4 days longer - Neuware -InhaltsangabeTuring-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.…