Read more
List of contents
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.- 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.
About the author
Prof. Dr. H.-D. Ebbinghaus ist Leiter des Instituts für Mathematische Logik an der Universität Freiburg. Durch Veröffentlichungen hat der Autor einen hohen Bekanntheitsgrad in der Hochschulmathematik.