Download e-book for iPad: Rekursive Funktionen by Heinz Lüneburg

By Heinz Lüneburg

Dieses Buch basiert auf Vorlesungen, die der Autor in Kaiserslautern gehalten hat. Ihr wesentliches Anliegen battle, die Turing-berechenbaren Wortfunktionen auf eine von jeglichem Maschinenmodell unabhängige Weise zu charakterisieren, nämlich als die partiell Wort-rekursiven Wortfunktionen. Wortfunktionen lassen sich mittels arithmetischer Funktionen darstellen und zwar so, dass die partiell rekursiven arithmetischen Funktionen den partiell Wort-rekursiven Wortfunktionen entsprechen, was once für sich gesehen schon nicht auf der Hand liegt. Auf diese Weise erhält guy den Begriff der Turing-Berechenbarkeit auch für arithmetische Funktionen. Der Satz additionally, dass die Turing-berechenbaren Wortfunktionen gerade die partiell rekursiven Wortfunktionen sind, ist überhaupt nicht selbstverständlich, so dass auf dem Wege zu diesem Satz eine ganze Reihe hoch interessanter weiterer Sätze zu beweisen sind. Dies alles ist hier aufgeschrieben.

Show description

Read or Download Rekursive Funktionen PDF

Similar german_4 books

Download PDF by Mahir B. Sayir, Jürg Dual, Stephan Kaufmann (auth.): Ingenieurmechanik 2: Deformierbare Körper

Der vorliegende zweite Band setzt die "Ingenieurmechanik" mit der Festigkeitslehre castle. Nach Einf? hrung der Grundbegriffe (Spannungstensor, Verschiebungsvektor, Verzerrungstensor) werden die Stoffgleichungen des linear elastischen okay? rpers besprochen. Die folgenden Kapitel behandeln Zug, Biegung und Torsion von Balken und St?

Handbuch der Feuerungstechnik und des Dampfkesselbetriebes: by Georg Herberg PDF

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer ebook information mit Publikationen, die seit den Anfängen des Verlags von 1842 erschienen sind. Der Verlag stellt mit diesem Archiv Quellen für die historische wie auch die disziplingeschichtliche Forschung zur Verfügung, die jeweils im historischen Kontext betrachtet werden müssen.

Dr.-Ing. Kurt Lange, Dr.-Ing. Heinz Meyer-Nolkemper (auth.)'s Gesenkschmieden PDF

Einführung. Grundlagen. Werkstoffe und Halbzeug. Gesenkschmiede-Verfahren. Werkzeuge zum Gesenkschmieden. Gesenkschmiedemaschinen. Arbeitsgänge im Gesenkschmiedebetrieb vor und nach dem Schmieden. Der Gesenkschmiedebetrieb. Das Gesenkschmiedestück. Schrifttum. Sachverzeichnis.

Extra info for Rekursive Funktionen

Example text

Der Graph von F ist rekursivaufzählbar. Es gibt also primitiv rekursive Funktionen a1, ... , a n +m , ß, so dass dieser Graph aus den (m + n + l)-Tupeln mit tE No besteht. Die Menge A besteht aus allen m-Tupeln für die ß(t) = 0 ist. Nach Satz 2 von Abschnitt 7 ist die Menge B der t mit ß(t) = 0 primitiv rekursiv, so dass diese Menge auch rekursiv aufzählbar ist. Es gibt also eine primitiv rekursive Funktion "( mit B = b(8) I 8 E No}. Es folgt A = {(a1"((8), ... , a m , "((8) 18 E No}, so dass Arekursiv aufzählbar ist.

Fn(x)) I x E No}. Setze F(x) :=c(/1(x), ... ,fn(x)). Dann ist F primitiv rekursiv. Ferner gilt c(A) = {F(x) I x E No}, so dass c(A) und damit A nach Satz 6 von Abschnitt 7 rekursivaufzählbar ist. Ist Arekursiv aufzählbar, so ist c(A) rekursivaufzählbar. Nach Satz 6 von Abschnitt 7 gibt es eine primitiv rekursive Funktion F mit c(A) = {F(x) I x E No}. Setzt man dann fi(X) := cni(F(x)). Dann ist rekursiv und es gilt A Ii für alle i primitiv = {(/1(x), ... ,fn(x)) I x E No}. 8. Rekursive und rekursiv au/zählbare Teilmengen von N ö 31 Damit ist alles gezeigt.

R(x)). Dann ist / primitiv rekursiv und es gilt Also ist A={J(X)IXENo}, so dass A nach Satz 6 rekursivaufzählbar ist. Satz 8. Vereinigung und Schnitt einer endlichen Anzahl rekursiv au/zählbarer Mengen sind rekursiv au/zählbar. Beweis. Es seien Al, ... , An rekursivaufzählbare Mengen. Es gibt dann zweistellige, primitiv rekursive Funktionen 11, ... , In, so dass h(a, x) = 0 genau dann eine Lösung x hat, wenn a E Ai ist. Dann gilt: 1) Es gibt genau dann ein n-Tupel Xl, ... , X n mit wenn a E UZ=l Ai ist.

Download PDF sample

Rated 4.87 of 5 – based on 41 votes