Algorithmentheorie [Paperback]

0: Einige Begriffe und Notationen.- 0.1 Mengen und Funktionen.- 0.1.1 Mengen.- 0.1.2 Funktionen.- 0.1.3 Einige spezielle Funktionen.- 0.2 Zeichen und Worte.- 0.2.1 Zeichenreihen und Worte.- 0.2.2 Wortfunktionen.- 0.2.3 Eine Bemerkung zur Interpretation.- 1 Grundbegriffe.- 1.1 Algorithmen.- 1.1.1 Der Begriff Algorithmus.- 1.1.2 Der Begriff der berechenbaren Funktion.- 1.1.2.1 Algorithmische und algebraische Definitionen.- 1.1.2.2 Berechenbare Funktionen.- 1.1.2.3 Der Fall der partiellen Funktionen.- 1.1.2.4 Algorithmen und berechenbare Funktionen.- 1.1.3 Eine Pr?zisierung des Begriffs Algorithmus.- 1.1.4 Algorithmentheorie.- 1.1.5 Historischer Hintergrund der Algorithmentheorie.- 1.1.6 Algorithmentheorie und Informatik.- 1.2 Abz?hlbarkeit.- 1.2.1 Einleitung.- 1.2.2 Abz?hlbare Mengen.- 1.2.3 Satz.- 1.2.4 Satz.- 1.2.5 Satz.- 1.2.6 Eine intuitive Erkl?rung.- 1.3 Abz?hlungen von Worten.- 1.3.1 Eine Abz?hlung von V*&..21.- 1.3.2 Eine Abz?hlung von V*n&..23.- 1.3.2.1 Einleitung.- 1.3.2.2 Eine Abz?hlung von Nn&..24.- 1.3.2.3 Eine Abz?hlung von V*n&..26.- 1.3.2.4 Bemerkung.- 1.3.3 Die Funktionen VnWm.- 1.3.4 Bemerkung.- 1.3.5 Satz.- 2: Die Turing-Maschine.- 2.1 Definition der Turing-Maschine.- 2.1.1 Der Grundgedanke.- 2.1.2 Das physikalische Modell.- 2.1.2.1 Die Maschine.- 2.1.2.2 Die Arbeitsweise.- 2.1.2.3 Die Definition einer Funktion.- 2.1.2.4 Der Speicher der Turing-Maschine.- 2.1.3 Die formale Definition.- 2.1.3.1 Die Maschine.- 2.1.3.2 Die Konfiguration.- 2.1.3.3 Die Funktion succ.- 2.1.3.4 Drei Relationen.- 2.1.3.5 Die von einer Turing-Maschine definierte Funktion.- 2.1.4 Beispiele.- 2.1.5 Berechenbare Funktionen.- 2.1.6 Die These von Turing.- 2.1.7 Eine wichtige Bemerkung.- 2.1.8 Eine weitere Bemerkung.- 2.1.9 Die Berechenbarkeit anderer Funktionen als Wortfunktionen.- 2.2 Einige spezielle Turing-Maschinen.- 2.2.1 Einleitung.- 2.2.2 Echte Startzust?nde und Endzust?nde.- 2.2.3 Normalisierte Turing-Maschinen.- 2.2.4 Reduktion des Zeichenvorrats einer Turing-Maschine.- l!