Selecta Mathematica II
Springer Berlin (Verlag)
978-3-540-04867-1 (ISBN)
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.
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.
| Erscheint lt. Verlag | 1.1.1970 |
|---|---|
| Reihe/Serie | Heidelberger Taschenbücher |
| Zusatzinfo | XII, 188 S. 1 Abb. |
| Verlagsort | Berlin |
| Sprache | deutsch |
| Maße | 133 x 203 mm |
| Gewicht | 250 g |
| Themenwelt | Mathematik / Informatik ► Mathematik |
| Schlagworte | Arithmetik • Beweis • Funktion • Lehrsatz • Mathematik |
| ISBN-10 | 3-540-04867-7 / 3540048677 |
| ISBN-13 | 978-3-540-04867-1 / 9783540048671 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
