Berechenbarkeit

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.- 2 Simple Funktionen.- 3 Elementare Funktionen.- 4 Primitiv rekursive Funktionen.- 5 Beschränkte Rekursion.- 6 Die Funktion von PETER.- 7 Universalfunktionen für FPF.- 8 Rekursion und Iteration.- 9 Grundbegriffe über ?-rekursive und partiell ?-rekursive Funktionen.- 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.- 11 Spracherweiterungen.- 12 PLA-programmierbare Funktionen.- 13 Die Sprache PLR und die primitiv rekursiven Funktionen.- 14 Die Schleifenhierarchie.- 15 FLR2 = FEF = FP2 und Konsequenzen daraus.- 16 Zeitfunktionen und Skalierungsfunktionen der Schleifenhierarchie.- 17 Kennzeichnungen der Schleifenhierarchie durch beschränkte Iterationen und Rekursionen.- 18 Die GRZEGORCZYK-Hierarchie.- 19 VLR1.- Supplement 7 Die Elimination von GOTOs.- III Rekursive und partiell rekursive Funktionen.- 20 Die Funktionenklasse F(R) einer Klasse R von Relationen.- 21 Die Struktur der rekursiv aufzählbaren Relationen.- 22 Rekursive Funktionen und rekursive Relationen.- 23 Partiell rekursive Funktionen.- 24 Eine Universalfunktion für PRF.- 25 Unentscheidbarkeiten.- 26 Uniformisierung.- 27 Die Arithmetisierung von Programmen.- 28 Der Gleichungskalkül von Herbrand-Gödel-Kleene . . ..- 29 Lösungen von Gleichungssystemen.- 30 Die Arithmetisierung des Gleichungskalküls.- Literatur.- Index der Begriffe und Namen.- Index der Symbole.