In der Berechenbarkeitstheorie sind die recursion Lehrsätze von Kleene ein Paar von grundsätzlichen Ergebnissen über die Anwendung berechenbarer Funktionen zu ihren eigenen Beschreibungen. Die Lehrsätze wurden zuerst von Stephen Kleene 1938 bewiesen.

Die zwei recursion Lehrsätze können angewandt werden, um geheftete Punkte von bestimmten Operationen auf berechenbaren Funktionen zu bauen, quines zu erzeugen, und über rekursive Definitionen definierte Funktionen zu bauen.

Der zweite recursion Lehrsatz

Der zweite recursion Lehrsatz ist nah mit Definitionen von berechenbaren Funktionen mit recursion verbunden. Weil es besser bekannt ist als der erste recursion Lehrsatz, wird es manchmal gerade den recursion Lehrsatz genannt. Seine Behauptung bezieht sich auf normalen Gödel numerierend φ der teilweisen rekursiven Funktionen, in denen die Funktion entsprechend dem Index e ist.

:The der zweite recursion Lehrsatz. Wenn F eine berechenbare Gesamtfunktion dann ist, gibt es einen solchen Index e dass.

Hier sind Mittel, dass, für jeden n, irgendein beide und, und ihre Werte definiert werden, gleich, oder beide unbestimmt sind.

Beispiel

Nehmen Sie an, dass g und h berechenbare Gesamtfunktionen sind, die in einer rekursiven Definition für eine Funktion f verwendet werden:

:

:

Diese rekursive Definition kann in eine berechenbare Funktion F (e) umgewandelt werden, der einen Index für ein Programm e nimmt und einen solchen Index F (e) dass zurückgibt

::

In diesem Zusammenhang ist ein fester Punkt von F ein solcher Index e dass; die durch solch einen e geschätzte Funktion wird eine Lösung der ursprünglichen recursion Gleichungen sein. Der recursion Lehrsatz gründet die Existenz solch eines festen Punkts, annehmend, dass F berechenbar ist, und manchmal den festen Punkt-Lehrsatz (von Kleene) aus diesem Grund genannt wird. Der Lehrsatz versichert nicht, dass e ein Index für den kleinsten festen Punkt der recursion Gleichungen ist; das ist die Rolle des ersten recursion Lehrsatzes, der unten beschrieben ist.

Beweis des zweiten recursion Lehrsatzes

Der Beweis verwendet eine besondere berechenbare Gesamtfunktion h, definiert wie folgt. In Anbetracht einer natürlichen Zahl x, h Produktionen der Index der teilweisen berechenbaren Funktion, die die folgende Berechnung durchführt:

:Given ein Eingang y, versuchen Sie zuerst zu rechnen. Wenn diese Berechnung eine Produktion e zurückgibt, dann schätzen Sie und geben Sie seinen Wert zurück, falls etwa.

So, für den ganzen x, wenn Halte, dann und wenn dann nicht hinkt, hinkt nicht; das wird angezeigt. Die Funktion h kann von der teilweisen berechenbaren Funktion und dem s-m-n Lehrsatz gebaut werden: Für jeden x, ist der Index eines Programms, das die Funktion schätzt.

Um den Beweis zu vollenden, lassen Sie F jede berechenbare Gesamtfunktion sein, und h als oben zu bauen. Lassen Sie e ein Index der Zusammensetzung sein, die eine berechenbare Gesamtfunktion ist. Dann durch die Definition von h.

Aber weil e ein Index, und so ist. Durch den transitivity bedeutet das. Folglich dafür.

Anwendung auf quines

Eine informelle Interpretation des zweiten recursion Lehrsatzes ist, dass jede teilweise berechenbare Funktion einen Index für sich erraten kann. Das folgt aus der folgenden Folgeerscheinung des Lehrsatzes (Cutland 1980:p. 202).

:Corollary. Für jede teilweise rekursive Funktion Q (x y) gibt es einen solchen Index p dass.

Die Folgeerscheinung wird durch das Lassen bewiesen, eine Funktion zu sein, die einen Index dafür gibt.

Die Folgeerscheinung zeigt, dass für jede berechenbare Funktion Q zwei Argumente es ein Programm gibt, das ein Argument nimmt und Q mit dem Index dieses wirklichen Programms als das erste Argument und das gegebene Argument als das zweite bewertet. Bemerken Sie, dass dieses Programm im Stande ist, seinen Index von der Information zu erzeugen, die in zum Programm gebaut ist; es verlangt keine Außenmittel, um den Index zu finden.

Ein klassisches Beispiel ist die Funktion Q (x, y) = x. Der entsprechende Index p gibt in diesem Fall eine berechenbare Funktion dass Produktionen sein eigener Index, wenn angewandt, auf jeden Wert nach (Cutland 1980:p. 204). Wenn ausgedrückt, als Computerprogramme sind solche Indizes als quines bekannt.

Das folgende Beispiel im Lispeln illustriert, wie der p in der Folgeerscheinung von der Funktion Q effektiv erzeugt werden kann. Die Funktion s11 im Code ist die Funktion dieses durch den S-m-n Lehrsatz erzeugten Namens.

Q kann zu jeder Zwei-Argumente-Funktion geändert werden.

(setq Q' (Lambda (x y) x))

(setq s11' (Lambda (f x) (verzeichnen 'Lambda' (y) (verzeichnen f x 'y))))

(setq n (verzeichnen 'Lambda' (x y) (haben Schlagseite Q (verzeichnen Sie s11 'x 'x) 'y)))

(setq p (eval (verzeichnen s11 n n)))

Die Ergebnisse der folgenden Ausdrücke sollten dasselbe sein.

φ _ p (Null)

(eval (verzeichnen p Null))

Q (p, Null)

(eval (verzeichnen Q p Null))

</Quelle>

Fester Punkt freie Funktionen

Eine Funktion F solch, der für den ganzen e festen freien Punkt genannt wird. Der recursion Lehrsatz zeigt, dass keine berechenbare Funktion Punkt frei befestigt wird, aber es gibt viele nichtberechenbarer fester Punkt freie Funktionen. Das Vollständigkeitskriterium von Arslanov stellt fest, dass das einzige rekursiv enumerable Grad von Turing, der einen festen Punkt freie Funktion schätzt, 0 , der Grad des stockenden Problems ist.

Der erste recursion Lehrsatz

Der erste recursion Lehrsatz ist mit festen Punkten verbunden, die von Enumerationsmaschinenbedienern bestimmt sind, die eine berechenbare Entsprechung von induktiven Definitionen sind. Ein Enumerationsmaschinenbediener ist eine Reihe von Paaren (A, n), wo A ist (Code für a), ist der begrenzte Satz von Zahlen und n eine einzelne natürliche Zahl. Häufig wird n als ein Code für ein befohlenes Paar von natürlichen Zahlen besonders angesehen, wenn Funktionen über Enumerationsmaschinenbediener definiert werden. Enumerationsmaschinenbediener sind von Hauptwichtigkeit in der Studie der Enumeration reducibility.

Jeder Enumerationsmaschinenbediener Φ bestimmt eine Funktion von Sätzen von naturals zu Sätzen von durch gegebenem naturals

:

Ein rekursiver Maschinenbediener ist ein Enumerationsmaschinenbediener, der, wenn gegeben, der Graph einer teilweisen rekursiven Funktion, immer den Graphen einer teilweisen rekursiven Funktion zurückgibt.

Ein fester Punkt eines Enumerationsmaschinenbedieners &Phi; ist ein Satz F solch dass &Phi; (F) = F. Der erste Enumerationslehrsatz zeigt, dass feste Punkte effektiv erhalten werden können, wenn der Enumerationsmaschinenbediener selbst berechenbar ist.

:First recursion Lehrsatz. Die folgenden Behauptungen halten.

:# Für jeden berechenbaren Enumerationsmaschinenbediener Φ gibt es rekursiv enumerable setzt solchen F, dass Φ (F) = F und F der kleinste Satz mit diesem Eigentum ist.

:# Für jeden rekursiven Maschinenbediener Ψ gibt es eine teilweise berechenbare Funktion φ solch, dass Ψ (φ) = φ und φ ist die kleinste teilweise berechenbare Funktion mit diesem Eigentum.

Beispiel

Wie der zweite recursion Lehrsatz kann der erste recursion Lehrsatz verwendet werden, um befriedigende Funktionssysteme von recursion Gleichungen zu erhalten. Um den ersten recursion Lehrsatz anzuwenden, müssen die recursion Gleichungen zuerst als ein rekursiver Maschinenbediener umgearbeitet werden.

Denken Sie die recursion Gleichungen für die Factorial-Funktion f:

:f (0) = 1,

:f (n+1) = (n + 1) &middot; f (n).

Der entsprechende rekursive Maschinenbediener &Phi; wird Information haben, die erzählt, wie man zum folgenden Wert von f vom vorherigen Wert kommt. Jedoch wird der rekursive Maschinenbediener wirklich den Graphen von f definieren. Erstens, &Phi; wird das Paar enthalten. Das zeigt an, dass f (0) unzweideutig 1 ist, und so das Paar (0,1) im Graphen von f ist.

Dann für jeden n und M, &Phi; wird das Paar enthalten. Das zeigt an, dass, wenn f (n) M ist, dann ist f (n + 1) (n + 1) M, so dass das Paar (n + 1 (n + 1) ist m) im Graphen von f. Verschieden vom Grundfall f (0) = 1 verlangt der rekursive Maschinenbediener etwas Information über f (n), bevor es einen Wert von f (n + 1) definiert.

Der erste recursion Lehrsatz (insbesondere Teil 1) stellt fest, dass es einen Satz F solch dass &Phi gibt; (F) = F. Der Satz F wird völlig aus befohlenen Paaren von natürlichen Zahlen bestehen, und wird der Graph der Factorial-Funktion f, wie gewünscht, sein.

Die Beschränkung zu recursion Gleichungen, die als rekursive Maschinenbediener umgearbeitet werden können, stellt sicher, dass die recursion Gleichungen wirklich einen am wenigsten festen Punkt definieren. Denken Sie zum Beispiel den Satz von recursion Gleichungen:

:g (0) = 1,

:g (n + 1) = 1,

:g (2n) = 0.

Es gibt keine Funktion g, diese Gleichungen befriedigend, weil sie g (2) = 2 einbeziehen und auch g (2) = 0 einbeziehen. So gibt es keinen festen Punkt g, diese recursion Gleichungen befriedigend. Es ist möglich, einen Enumerationsmaschinenbediener entsprechend diesen Gleichungen zu machen, aber es wird kein rekursiver Maschinenbediener sein.

Probeskizze für den ersten recursion Lehrsatz

Der Beweis des Teils 1 des ersten recursion Lehrsatzes wird durch das Wiederholen des Enumerationsmaschinenbedieners &Phi erhalten; der Anfang mit dem leeren Satz. Erstens wird eine Folge F, dafür gebaut. Lassen Sie F der leere Satz sein. Das Verfahren induktiv, für jeden k, hat F sein lassen. Schließlich wird F genommen, um zu sein. Der Rest des Beweises besteht aus einer Überprüfung, dass F rekursiv enumerable ist und der am wenigsten feste Punkt &Phi ist;. die Folge F verwendet in diesem Beweis entspricht der Kette von Kleene im Beweis des Fixpunktsatzes von Kleene.

Der zweite Teil des ersten recursion Lehrsatzes folgt aus dem ersten Teil. Die Annahme das &Phi; ist ein rekursiver Maschinenbediener wird verwendet, um dass der feste Punkt &Phi zu zeigen; ist der Graph einer teilweisen Funktion. Der Stichpunkt ist dass, wenn der feste Punkt F nicht der Graph einer Funktion ist, dann gibt es einen solchen k, dass F nicht der Graph einer Funktion ist.

Vergleich zum zweiten recursion Lehrsatz

Im Vergleich zum zweiten recursion Lehrsatz erzeugt der erste recursion Lehrsatz einen stärkeren Beschluss, aber nur wenn schmalere Hypothesen zufrieden sind. Rogers [1967] gebraucht den Begriff schwacher recursion Lehrsatz für den ersten recursion Lehrsatz und starken recursion Lehrsatz für den zweiten recursion Lehrsatz.

Ein Unterschied zwischen den ersten und zweiten recursion Lehrsätzen ist, dass, wie man versichert, die festen durch den ersten recursion Lehrsatz erhaltenen Punkte Punkte am wenigsten befestigt werden, während diejenigen, die beim zweiten recursion Lehrsatz erhalten sind, Punkte nicht am wenigsten befestigt werden dürfen.

Ein zweiter Unterschied ist, dass der erste recursion Lehrsatz nur für Gleichungssysteme gilt, die als rekursive Maschinenbediener umgearbeitet werden können. Diese Beschränkung ist der Beschränkung dauernden Maschinenbedienern im Fixpunktsatz von Kleene der Ordnungstheorie ähnlich. Der zweite recursion Lehrsatz kann auf jede rekursive Gesamtfunktion angewandt werden.

Verallgemeinerter Lehrsatz durch A.I. Maltsev

Anatoly Maltsev hat eine verallgemeinerte Version des recursion Lehrsatzes für jeden Satz mit einem vorganzen Numerieren bewiesen. Ein numerierender Gödel ist ein vorganzes Numerieren auf dem Satz von berechenbaren Funktionen, so gibt der verallgemeinerte Lehrsatz den Lehrsatz von Kleene recursion als ein spezieller Fall nach.

In Anbetracht eines vorganzen Numerierens dann für jede teilweise berechenbare Funktion mit zwei Rahmen dort besteht eine berechenbare Gesamtfunktion mit einem solchem Parameter dass

:

Siehe auch

• Semantik von Denotational, wo ein anderer am wenigsten fester Punkt-Lehrsatz zu demselben Zweck wie der erste recursion Lehrsatz verwendet wird.
• Fester Punkt combinators, die in der Lambda-Rechnung zu demselben Zweck wie der erste recursion Lehrsatz verwendet werden.
• Cutland, N.J. Berechenbarkeit: Eine Einführung in die rekursive Funktionstheorie, Universität von Cambridge Presse, 1980. Internationale Standardbuchnummer 0-521-29465-7
• Kleene, Stephen, "Auf der Notation für Ordinalzahlen," Die Zeitschrift der Symbolischen Logik, 3 (1938), 150-155.
• Rogers, H. Die Theorie von Rekursiven Funktionen und Wirksamer Berechenbarkeit, MIT Presse. Internationale Standardbuchnummer 0-262-68052-1; internationale Standardbuchnummer 0-07-053522-1

Außenverbindungen

• .