Berechenbarkeit: Rekursive und Programmierbare Funktionen by Walter Felscher

By Walter Felscher

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

Show description

Read Online or Download Berechenbarkeit: Rekursive und Programmierbare Funktionen PDF

Similar machine theory books

Control of Flexible-link Manipulators Using Neural Networks

Regulate of Flexible-link Manipulators utilizing Neural Networks addresses the problems that come up in controlling the end-point of a manipulator that has an important volume of structural flexibility in its hyperlinks. The non-minimum section attribute, coupling results, nonlinearities, parameter diversifications and unmodeled dynamics in this sort of manipulator all give a contribution to those problems.

Fouriertransformation für Ingenieur- und Naturwissenschaften

Dieses Lehrbuch wendet sich an Studenten der Ingenieurfächer und der Naturwissenschaften. Durch seinen systematischen und didaktischen Aufbau vermeidet es ungenaue Formulierungen und legt so die Grundlage für das Verständnis auch neuerer Methoden. Indem die klassische und die Funktionalanalysis auf der foundation des Fourieroperators zusammengeführt werden, vermittelt es ein fundiertes und verantwortbares Umgehen mit der Fouriertransformation.

Automated Theorem Proving: Theory and Practice

Because the twenty first century starts off, the ability of our magical new instrument and companion, the pc, is expanding at an amazing fee. desktops that practice billions of operations according to moment at the moment are usual. Multiprocessors with millions of little pcs - rather little! -can now perform parallel computations and clear up difficulties in seconds that very few years in the past took days or months.

Practical Probabilistic Programming

Functional Probabilistic Programming introduces the operating programmer to probabilistic programming. during this ebook, you are going to instantly paintings on sensible examples like construction a unsolicited mail filter out, diagnosing machine procedure facts difficulties, and convalescing electronic photographs. you will discover probabilistic inference, the place algorithms help in making prolonged predictions approximately concerns like social media utilization.

Extra info for Berechenbarkeit: Rekursive und Programmierbare Funktionen

Sample text

Ein Ausweg aus dieser MiBlichleit besteht darin, diese Funktionswerte in einer einzigen Zahl zu kodieren, und in der Tat fUhrt die Historie Hf HISTORIE UND WERTVERLAUFSREKURSION 53 gerade eine solche Kodierung dureh. Ieh definiere deshalb, daB fk+l aus gk und rk+2 dureh Wertverlaufsrekursion bestimmt sei, wenn (W) fk+l(a,O)=gk(a) fk+l(a, n+1) = rk+2(a, n, Hfk+l(a,n)) gilt. Ieh werde nun zeigen, daB es zu gegebenen gk und rk+2 die Funktion fk+l mit (W) eindeutig bestimmt ist, und daB, weiter, jede primitiv rekursiv abgeschlossene Klasse auch unter dieser Wertverlaufsrekursion abgeschlossen ist.

Dazu brauche ich nur (FSF2) nachzupriifen. Sei also R k+l in R(F), und seien Funktionen g und f durch g( a,i) = II < CSG 0 xa( a,j) I j ~ i> und f( a,n) = E< g( a,i) I i < n> erklart; sie beide sind in F . Es gilt aber g( a,i) = 1 genau dann, wenn, fUr alle j~ i, das Paar nicht in Rk+l ist. Beginnend mit 0, tragt jedes soIehe i nun 1 zu f( a,n) bei, und also ist f gleich Il

E. den Mengen aller i mit i < n) definiert sind. Offenbar lassen sich solche Funktionen als die Folgen ihrer Funktionswerte auffassen. Da ich n hier aber nicht fixieren will, muB ich mich zu ihrer Kodierung eines anderen Verfahrens bedienen, namlich der elementaren Kodierung durch die Exponentenfolgen von Primfaktorzerlegungen, die ich schon im Kapitel 3 besprochen hatte. Das wesentliche Werkzeug fUr diese Arithmetisierungen ist die Historie H fk +1 einer Funktion fk +1, die ich als Hfk+l( a,n) = II definiere.

Download PDF sample

Rated 4.59 of 5 – based on 12 votes