Table of Contents
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.- 2.2.5 Turing-Maschinen mit mehreren Bändern.- 2.2.6 Eine äquivalente Definition der Berechenbarkeit für Funktionen mit n tupeln als Werte.- 2.3 Die universelle Turing-Maschine.- 2.3.1 Der Grundgedanke.- 2.3.2 Die Beschreibung einer Turing-Maschine mittels eines Wortes.- 2.3.2.1 Der Zeichenvorrat W.- 2.3.2.2 Das Wort DET.- 2.3.2.3 Beispiele.- 2.3.2.4 Die V-Beschreibung.- 2.3.3 Weitere Definitionen und Notationen.- 2.3.3.1 Die Mengen DE und D.- 2.3.3.2 Die Turing-Maschinen TE(x) und T(x).- 2.3.3.3 Gödel-Nummer.- 2.3.4 Die universelle Turing-Maschine.- 2.3.4.1 Simulation einer Turing-Maschine.- 2.3.4.2 Eine universelle Turing-Maschine.- 2.3.5 Kommentar.- 2.3.6 Konstruktionen mit Turing-Maschinen.- 2.4 Einige nicht-berechenbare Funktionen.- 2.4.1 Das Halteproblem.- 2.4.2 Das Halteproblem bei leerem Band.- 2.4.3 Das uniforme Halteproblem.- 2.4.4 Das Äquivalenzproblem.- 2.4.5 Schlußbemerkung.- 2.5 Rekursiv-aufzählbare und rekursive Mengen.- 2.5.1 Definitionen.- 2.5.2 Der Bildbereich einer totalen berechenbaren Funktion.- 2.5.3 Die Akzeptorfunktion.- 2.5.4 Die Beziehung zwischen rekursiv-aufzählbaren und rekursiven Mengen.- 2.5.5 Beispiele von Mengen, die rekursiv-aufzählbar, aber nicht rekursiv sind.- 2.5.6 Beispiele von Mengen, die nicht rekursiv-aufzählbar sind.- 2.5.7 Quantifizierungen von Mengen.- 2.5.8 Effektive Abzählungen von Funktionen und Mengen.- 2.5.8.1 Die berechenbaren Funktionen.- 2.5.8.2 Die rekursiv-aufzählbaren Mengen.- 2.5.8.3 Bemerkung.- 2.5.9 Kommentar.- 2.5.9.1 Ein praktischer Aspekt.- 2.5.9.2 Eine graphische Darstellung.- 2.5.9.3 Über die Natur von rekursiv-aufzählbaren und rekursiven Mengen.- 2.5.9.4 Axiomatische Systeme.- 2.5.9.5 Über die Nützlichkeit partieller Funktionen.- 3: Andere Formalismen als Turing-Maschinen.- 3.1 Die rekursiven Funktionen.- 3.1.1 Einleitung.- 3.1.2 Definition.- 3.1.2.1 Die axiomatische Definitionsmethode.- 3.1.2.2 Die Basisfunktionen.- 3.1.2.3 Die Komposition.- 3.1.2.4 Die Rekursion.- 3.1.2.5 Die Minimalisierung.- 3.1.2.6 Definitionen.- 3.1.2.7 Satz.- 3.1.2.8 Wichtige Bemerkungen.- 3.1.3 Beispiele.- 3.1.4 Endliche Funktionen.- 3.1.5 Das Ziel der nächsten Abschnitte.- 3.1.6 Fallunterscheidung.- 3.1.7 Erweiterte Initialisierung.- 3.1.8 Simultane Rekursion.- 3.1.9 Rekursion mit variablen Schritten.- 3.1.10 Reduktion des Zeichenvorrats.- 3.1.11 Die Äquivalenz von berechenbaren und rekursiven Funktionen.- 3.1.12 Wortbeschreibungen, die universelle rekursive Funktion und unlösbare Probleme.- 3.1.12.1 Wortbeschreibungen.- 3.1.12.2 Satz.- 3.1.12.3 Unlösbare Probleme.- 3.1.13 Verallgemeinerung für andere Funktionen als Wortfunktionen.- 3.1.14 Satz.- 3.2 Die Markov-Algorithmen.- 3.2.1 Einleitung.- 3.2.2 Definitionen.- 3.2.2.1 Der Markov-Algorithmus.- 3.2.2.2 Informelle Beschreibung des Markov- Algorithmus.- 3.2.2.3 Drei Relationen.- 3.2.2.4 Die von einem Markov-Algorithmus definierte Funktion.- 3.2.2.5 Markov-berechenbare Funktionen.- 3.2.3 Beispiele.- 3.2.4 Die Äquivalenz mit Turing-Maschinen.- 3.2.5 Bemerkung.- 4: Nicht-deterministische Algorithmen und Grammatiken.- 4.1 Die Begriffe.- 4.1.1 Nicht-deterministische Algorithmen.- 4.1.2 Die formale Definition nicht-deterministischer Algorithmen.- 4.1.3 Grammatiken.- 4.1.4 Axiomatische Systeme.- 4.2 Semi-Thue-Algorithmen und semi-Thue-Grammatiken.- 4.2.1 Semi-Thue-Algorithmen.- 4.2.1.1 Informelle Beschreibung.- 4.2.1.2 Formale Definition.- 4.2.1.3 Beispiele.- 4.2.2 Semi-Thue-Grammatiken.- 4.2.2.1 Einleitung.- 4.2.2.2 Formale Definition.- 4.2.2.3 Beispiel.- 4.2.2.4 Kontextfreie Grammatiken.- 4.2.3 Semi-Thue-Grammatiken und rekursiv-aufzählbare Mengen.- 4.2.4 ?-freie semi-Thue-Grammatiken.- 4.2.5 Weiterentwicklung der Theorie.- 4.2.6 Das Korrespondenzproblem von Post.- Eine Schlußbemerkung.- Literatur.- Lösungen und Lösungshinweise der wichtigsten Übungen.- Die wichtigsten Notationen.- Alphabetische Liste der wichtigsten Funktionen.- Alphabetisches Sachregister.
