Berechenbarkeit

Rekursive und Programmierbare Funktionen

Walter Felscher (Autor)

Buch | Softcover

XI, 478 Seiten

1993
Springer Berlin (Verlag)
978-3-540-56354-9 (ISBN)

Artikel merken

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.

Erscheint lt. Verlag	30.8.1993
Reihe/Serie	Springer-Lehrbuch
Zusatzinfo	XI, 478 S.
Verlagsort	Berlin
Sprache	deutsch
Maße	155 x 235 mm
Gewicht	752 g
Themenwelt	Mathematik / Informatik ► Informatik ► Betriebssysteme / Server
	Informatik ► Software Entwicklung ► User Interfaces (HCI)
	Mathematik / Informatik ► Informatik ► Theorie / Studium
	Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
Schlagworte	Berechenbarkeit • Beweis • Funktion • Geometrie • Gleichung • Gleichungskalkül • Hierarchien • Logik • Mathematik • Programmierbare Funktionen • Rekursion • Rekursive Funktionen • Relationen • Zahlentheorie
ISBN-10	3-540-56354-7 / 3540563547
ISBN-13	978-3-540-56354-9 / 9783540563549
Zustand	Neuware