Berechenbarkeit

I Rekursive Funktionen.- 1 Terminologie und grundlegende Konstruktionen.- 1. Funktionen und Folgen.- 2. Superposition.- 3. Fundamentale Konstruktionen.- 4. Übersetzungsregeln.- 5. Appendix: Lokale Superposition.- 2 Simple Funktionen.- Schemata und Funktionale.- 3 Elementare Funktionen.- 4 Primitiv rekursive Funktionen.- 1. Die Klassen FPm.- 2. Historie und Wertverlaufsrekursion.- 3. Simultane Rekursion.- 4. Appendix: EXP(0,x) liegt in FP2.- 5 Beschränkte Rekursion.- 1. G-beschränkte Klassen.- 2. Kennzeichnung elementar abgeschlossener Klassen.- 6 Die Funktion von PETER.- 7 Universalfunktionen für FPF.- 8 Rekursion und Iteration.- Explizite Reduktionsverfahren.- 9 Grundbegriffe über ?-rekursive und partiell ?-rekursive Funktionen.- 1. ?-rekursive Funktionen.- 2. Schemata, Funktionale und Berechnungen.- 3. Partiell ?-rekursive Funktionen.- 4. Terminanten.- Supplement 1 Ein Gleichungskalkül für primitiv recursive Funktionen.- Supplement 2 Rekursion mit Substitution der Parameter.- Supplement 3 Geschachtelte Rekursion.- Supplement 4 Mehrfache Rekursion.- Supplement 5 Geschachtelte 2-fache Rekursion.- Supplement 6 Iteration 1-stelliger Funktionen.- II Programmierbare Funktionen.- 10 Die Sprache PLA.- 1. Syntax von PLA.- 2. Semantik von PLA.- 3. Berechnungen mit PLA.- 4. Die von einem Programm programmierte Funktion und ihre T-Darstellung.- 5. Die Komponenten der Berechnungsfunktionen liegen in FP3.- 6. Eine Berechnungsfunktion in FP2.- 11 Spracherweiterungen.- Appendix: Weiteres über Erweiterungen mit Operationsanweisungen.- 12 PLA-programmierbare Funktionen.- 13 Die Sprache PLR und die primitiv rekursiven Funktionen.- PLRS-Programme.- 14 Die Schleifenhierarchie.- Die Programmierung der Berechnungsfunktion.- 15 FLR2 = FEF = FP2 und Konsequenzen daraus.- Elementare Zeitfunktionen für elementare Funktionen.- 16 Zeitfunktionen und Skalierungsfunktionen der Schleifenhierarchie.- 17 Kennzeichnungen der Schleifenhierarchie durch beschränkte Iterationen und Rekursionen.- 18 Die GRZEGORCZYK-Hierarchie.- 19 VLR1.- Entscheidbarkeitsfragen.- Supplement 7 Die Elimination von GOTOs.- 1. Zur Geometrie der P-Folgen.- 2. Das Verhältnis zweier Stellen.- 3. Voranschreitende GOTOs.- 4. Zurückspringende GOTOs.- III Rekursive und partiell rekursive Funktionen.- 20 Die Funktionenklasse F(R) einer Klasse R von Relationen.- 1. Entr’acte: Zwei Fakten aus der Zahlentheorie.- 2. Die Kodierung endlicher Folgen durch die Gödelsche ?-Funktion.- 3. Klassen R mit primitiv rekursiv abgeschlossenem F(R) . . . ..- 21 Die Struktur der rekursiv aufzählbaren Relationen.- 1. Beschränkte arithmetische Relationen ..- 2. Projektionen.- 3. P-abgeschlossene Klassen und ihr Kern.- 4. Rekursiv aufzählbare Relationen.- 22 Rekursive Funktionen und rekursive Relationen.- 1. Rekursiv abgeschlossene Klassen.- 2. Abgeschlossenheit unter Minimierungen.- 23 Partiell rekursive Funktionen.- 24 Eine Universalfunktion für PRF.- Totale Funktionen.- Appendix: Geschachtelte mehrfache Rekursion.- Terme.- 25 Unentscheidbarkeiten.- 26 Uniformisierung.- 1. Uniformisierungen und universelle Folgen.- 2. Fixpunktsatz und Rekursionstheorem.- 3. Isomorphiesätze.- 27 Die Arithmetisierung von Programmen.- 1. Arithmetische Kodierung.- 2. Arithmetisierung der Syntax von PLA.- 3. Arithmetisierung von PLA-Berechnungen.- 4. Universalität und Uniformisierung.- 28 Der Gleichungskalkül von Herbrand-Gödel-Kleene . . ..- 1. Der Gleichungskalkül.- 2. Abhängigkeit von Funktionssymbolen.- 3. Definierbarkeit von Funktionen.- 4. Partiell ?-rekursive Funktionen sind gleichungsdefinierbar . . ..- 5. Durch Gleichungssysteme erzeugte Funktionale.- 6. Beispiele, insbesondere vom Nutzen partieller Funktionen.- 29 Lösungen von Gleichungssystemen.- 1. Die Operatoren AG,f,? und ihre Fixpunkte.- 2. Beispiele.- 3. Fixpunkte sind gleichungsdefiniert.- 4. Sukzessive Approximation von Lösungen.- 5. Semantische Lösungen von Gleichungsmengen.- 6. Bedingungen für die Auswertbarkeit von Termen.- 7. Syntaktische Lösungen sind semantische Lösungen.- 30 Die Arithmetisierung des Gleichungskalküls.- 1. Die Arithmetisierung von Bäumen.- 2. Die Arithmetisierung von Termen.- 3. Die Arithmetisierung von Deduktionen.- 4. Uniformisierung und Universalfunktionen.- 5. Appendix: Weiteres über Kodierungen.- g-adische Kodierung.- Kodierung durch Paarungsfunktionen.- Vertikale Kodierung.- Literatur.- Index der Begriffe und Namen.- Index der Symbole.