Berechenbarkeit: Rekursive und Programmierbare Funktionen by Walter Felscher

By Walter Felscher

Dieses Lehrbuch behandelt verständlich, umfassend und smooth 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 information angereicherte und an neuesten Ergebnissen orientierte Darstellung.

Show description

Read or Download Berechenbarkeit: Rekursive und Programmierbare Funktionen (Springer-Lehrbuch) (German Edition) PDF

Best machine theory books

Theoretical Aspects of Distributed Computing in Sensor Networks

Instant advert hoc sensor networks has lately turn into a really lively examine topic. reaching effective, fault-tolerant realizations of very huge, hugely dynamic, advanced, unconventional networks is a true problem for summary modelling, algorithmic layout and research, yet an excellent foundational and theoretical historical past seems missing.

The Logic of Time: A Model-Theoretic Investigation into the Varieties of Temporal Ontology and Temporal Discourse (Synthese Library)

The topic of Time has a large highbrow attraction throughout varied dis­ ciplines. This has proven within the number of reactions bought from readers of the 1st variation of the current e-book. Many have reacted to concerns raised in its philosophical discussions, whereas a few have even solved some of the open technical questions raised within the logical elaboration of the latter.

The Rational Expectation Hypothesis, Time-Varying Parameters and Adaptive Control: A Promising Combination? (Advances in Computational Economics)

One of many significant controversies in macroeconomics during the last 30 years has been that at the effectiveness of stabilization regulations. besides the fact that, this debate, among those that think that this type of regulations is lifeless if now not damaging and people who argue in desire of it, has been usually theoretical up to now.

Extra info for Berechenbarkeit: Rekursive und Programmierbare Funktionen (Springer-Lehrbuch) (German Edition)

Sample text

Foiglich konnen elementar abgeschlossene Klassen auch dadurch definiert werden, daB man das Verlangen des Vorhandenseins von'" durch dasjenige des Vorhandenseins von CS und CSG ersetzt. =II sind ele- men tare Funktionen . Aus der ersten Definition folgt in der Tat X O = 1 und x Y+1 = x Y. x. 1m Besonderen ist auch fUr jedes n nun nY=(xY)o elementar, also auch fUr jede Funktion g(y) aus F dann n g (y) in F. Aus (FSI8) folgt nun, daB 2 Y eine elementare, aber nicht simple Funktion ist.

FUr n >0 schlielHich ist x = n+1 iiquivalent zu eS(x) = n, weshalb dann Xn+l = Xn 0 es . xf:o (FP3) FP 1 enthiilt die charakteristischen Funktionen der Mengen {n}xw k . Denn das sind die Funktionen Xn op~+l. (FP4) FUr m~ 1 ist R(FP m) Boolesch abgeschlossen und enthalt aile endlichen Mengen. (FS5), (FS9) (FP5) FUr m~ 1 ist FP m abgeschlossen unter Definitionen durch Fallunterscheidungen, die sich auf Relationen aus R(FP m) bez)ehen. Primitiv rekursive Definitionen mit Fallunterscheidungen, die sich auf Relationen aus R(FP m) beziehen, fUhren von FP m immer noch nur nach FP m+1 .

Ebenso machen es Paarungsfunktionen moglich, Relationen verschiedener SteIlenzahlen ineinander zu iiberfUhren: ist R I das Bild von R k unter AUk, und sind Xl, Xk die charakteristischen Funktionen von RI, Rk, so gilt Xk = Xl oAU k, weshalb zusammen mit R lauch R k in R(F) liegt. 1m bijektiven FaIle habe ich umgekehrt die Darstellung Xl = X k 0 UA k, so daB dann zusammen mit R k auch R I in R(F) liegt. Eine weitere, gelegentlich niitzliche Konstruktion ist (FS17) 1st fk+l in F so ist das auch die Funktion MAX fk+l der beschrankten Maximumsbildung mit MAXfk+l(a,n) = max .

Download PDF sample

Rated 4.94 of 5 – based on 26 votes