Berechenbarkeit : Rekursive und Programmierbare Funktionen

Dieses Lehrbuch behandelt verständlich, umfassend und modern die Theorie der Berechenbarkeit, ein klassisches Gebiet der Mathematischen Logik, das als Grundlagengebiet auch für die Informatik von höchster Bedeutung ist. Lebendig und didaktisch klar wird das Studium der berechenbaren Funktionen auf dem Programmbegriff aufgebaut. Dabei sind die Induktion als Beweisprinzip und die Rekursion als Konstruktionsprinzip die beiden grundlegenden Werkzeuge für den Umgang mit Zahlen und Funktionen. Obwohl über eine gewisse Vertrautheit mit der mathematischen Argumentationsweise hinaus keine inhaltlichen Kenntnisse aus der Mathematik oder der Informatik vorausgesetzt werden, findet auch der Kenner eine durch viele neuartige Details angereicherte und an neuesten Ergebnissen orientierte Darstellung.

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.