Overview

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.

Full Product Details

Author:   Walter Felscher
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Dimensions:   Width: 15.50cm , Height: 2.50cm , Length: 23.50cm
Weight:   0.765kg
ISBN:  

9783540563549

ISBN 10:   3540563547
Pages:   478
Publication Date:   30 August 1993
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Out of stock  
The supplier is temporarily out of stock of this item. It will be ordered for you on backorder and shipped when it becomes available.
Language:   German

Table of Contents

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions