Berechenbarkeit
Rekursive und Programmierbare Funktionen
1st Edition
Published on 30. August 1993
Book
Paperback/Softback
XI, 478 pages
978-3-540-56354-9 (ISBN)
Description
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.
More details
Series
Language
German
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Upper undergraduate
Illustrations
XI, 478 S.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 27 mm
Weight
739 gr
ISBN-13
978-3-540-56354-9 (9783540563549)
DOI
10.1007/978-3-642-78019-6
Schweitzer Classification
Other editions
Additional editions
E-Book
03/2013
Springer
€36.99
Available for download
Content
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.