Selecta Mathematica II [Paperback]

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 IIII.- 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_}}D_T^0$$.- ? 7. Lemma: Wenn M(T) angesetzt auf das leere Band, unendlich lange l?uft, ist das Eck-Dominospiel $${D_}}D_T^0$$ gut.- ? 8. Lemma: Wenn das Eck-Dominospiel $${D_}}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 01-Folgen.- ? 1. Die Kolmogorovsche KomlC3