Inhalt
0: Einige Begriffe und Notationen.- 0.1 Mengen und Funktionen.- 0.2 Zeichen und Worte.- 1 Grundbegriffe.- 1.1 Algorithmen.- 1.2 Abzählbarkeit.- 1.3 Abzählungen von Worten.- 2: Die Turing-Maschine.- 2.1 Definition der Turing-Maschine.- 2.2 Einige spezielle Turing-Maschinen.- 2.3 Die universelle Turing-Maschine.- 2.4 Einige nicht-berechenbare Funktionen.- 2.5 Rekursiv-aufzählbare und rekursive Mengen.- 3: Andere Formalismen als Turing-Maschinen.- 3.1 Die rekursiven Funktionen.- 3.2 Die Markov-Algorithmen.- 4: Nicht-deterministische Algorithmen und Grammatiken.- 4.1 Die Begriffe.- 4.2 Semi-Thue-Algorithmen und semi-Thue-Grammatiken.- Eine Schlußbemerkung.- Literatur.- Lösungen und Lösungshinweise der wichtigsten Übungen.- Die wichtigsten Notationen.- Alphabetische Liste der wichtigsten Funktionen.- Alphabetisches Sachregister.