Selecta Mathematica II [Paperback]

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 IIII.- 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.- lÃF