In der mathematischen Logik und Informatik sind die μ-Recursive-Funktionen eine Klasse von teilweisen Funktionen von natürlichen Zahlen bis natürliche Zahlen, die in einem intuitiven Sinn "berechenbar" sind. Tatsächlich in der Berechenbarkeitstheorie wird es gezeigt, dass die μ-Recursive-Funktionen genau die Funktionen sind, die durch Maschinen von Turing geschätzt werden können. Die μ-Recursive-Funktionen sind nah mit primitiven rekursiven Funktionen verbunden, und ihre induktive Definition baut (unten) auf diese der primitiven rekursiven Funktionen. Jedoch ist nicht jede μ-Recursive-Funktion eine primitive rekursive Funktion - das berühmteste Beispiel ist die Funktion von Ackermann.

Andere gleichwertige Klassen von Funktionen sind λ-recursive Funktionen und die Funktionen, die durch Algorithmen von Markov geschätzt werden können.

Der Satz aller rekursiven Funktionen ist als R in der rechenbetonten Kompliziertheitstheorie bekannt.

Definition

Die μ-Recursive-Funktionen (oder teilweisen μ-Recursive-Funktionen) sind teilweise Funktionen, die begrenzte Tupel von natürlichen Zahlen nehmen und eine einzelne natürliche Zahl zurückgeben. Sie sind die kleinste Klasse von teilweisen Funktionen, die die anfänglichen Funktionen einschließt und unter der Zusammensetzung, primitivem recursion und dem μ Maschinenbediener geschlossen wird.

Die kleinste Klasse von Funktionen einschließlich der anfänglichen Funktionen und geschlossen unter der Zusammensetzung und primitivem recursion (d. h. ohne minimisation) ist die Klasse von primitiven rekursiven Funktionen. Während alle primitiven rekursiven Funktionen ganz sind, trifft das auf teilweise rekursive Funktionen nicht zu; zum Beispiel ist der minimisation der Nachfolger-Funktion unbestimmt. Der Satz von rekursiven Gesamtfunktionen ist eine Teilmenge der teilweisen rekursiven Funktionen und ist eine Obermenge der primitiven rekursiven Funktionen; wie man beweisen kann, sind Funktionen wie die Funktion von Ackermann rekursiv, und nicht primitiv ganz.

Die ersten drei Funktionen werden die "anfänglichen" oder "grundlegenden" Funktionen genannt: (Im folgenden ist der subscripting pro Kleene (1952) p. 219. Für mehr über einige der verschiedenen in der Literatur gefundenen Symboliken sieh Symbolik unten.)

1. Unveränderliche Funktion: Für jede natürliche Zahl und jeden:

:.

1. :Alternative-Definitionen verwenden Zusammensetzungen der Nachfolger-Funktion und verwenden eine Nullfunktion, die immer Null im Platz der unveränderlichen Funktion zurückgibt.
2. Nachfolger-Funktion S:

:

1. Vorsprung-Funktion (hat auch die Identitätsfunktion genannt): Für alle solche natürlichen Zahlen dass:

:.

1. Zusammensetzungsmaschinenbediener (hat auch den Ersatz-Maschinenbediener genannt): In Anbetracht einer M ary Funktion und M k-ary Funktionen:

:.

1. Primitiver recursion Maschinenbediener: In Anbetracht der K-Ary-Funktion und des k+2-ary Funktion:
2. :

\rho (g, h) &\\stackrel {\\mathrm {def}} {=} f (y, x_1, \ldots, x_k) \quad {\\rm wo} \\

f (0, x_1, \ldots, x_k) &= g (x_1, \ldots, x_k) \\

f (y+1, x_1, \ldots, x_k) &= h (y, f (y, x_1, \ldots, x_k), x_1, \ldots, x_k) \, {richten} \end </Mathematik> {aus}.

1. Maschinenbediener von Minimisation: In Anbetracht (k+1)-ary Gesamtfunktion:

:

\mu (f) (x_1, \ldots, x_k) = z &\\stackrel {\\mathrm {def}} {\\iff }\\\exists y_0, \ldots, y_z \quad {\\rm such\dass }\\\

y_i &= f (ich, x_1, \ldots, x_k) \quad {\\rm für }\\i=0, \ldots, z \\

y_i &> 0 \quad {\\rm für }\\i=0, \ldots, z-1 \\

y_z &= 0

\end {richten} </Mathematik> {aus}

1. :Intuitively, minimisation sucht - Anfang der Suche von 0 und das Verfahren aufwärts - das kleinste Argument, das die Funktion verursacht, Null zurückzugeben; wenn es kein solches Argument gibt, endet die Suche nie.

Der starke Gleichheitsmaschinenbediener kann verwendet werden, um teilweise μ-Recursive-Funktionen zu vergleichen. Das wird für alle teilweisen Funktionen f und g so dass definiert

:

hält, ob, und nur wenn für jede Wahl von Argumenten entweder beide Funktionen definiert werden und ihre Werte gleich sind oder beide Funktionen, sind unbestimmt.

Gleichwertigkeit mit anderen Modellen der Berechenbarkeit

In der Gleichwertigkeit von Modellen der Berechenbarkeit wird eine Parallele zwischen Maschinen von Turing gezogen, die für bestimmte Eingänge und ein unbestimmtes Ergebnis für diesen Eingang in der entsprechenden teilweisen rekursiven Funktion nicht enden.

Der unbegrenzte Suchmaschinenbediener ist durch die Regeln von primitivem recursion nicht definierbar, weil diejenigen keinen Mechanismus für "unendliche Schleifen" (unbestimmte Werte) zur Verfügung stellen.

Normaler Form-Lehrsatz

Ein normaler Form-Lehrsatz wegen Kleenes sagt, dass für jeden k es primitive rekursive Funktionen und solch dass für jede μ-Recursive-Funktion mit k freien Variablen gibt, gibt es einen solchen e dass

:.

Die Nummer e wird einen Index oder Zahl von Gödel für die Funktion f genannt. Eine Folge dieses Ergebnisses ist, dass jede μ-Recursive-Funktion mit einem einzelnen Beispiel des μ auf eine (ganze) primitive rekursive Funktion angewandten Maschinenbedieners definiert werden kann.

Minsky (1967) beobachtet (wie Boolos-Burgess-Jeffrey (2002) Seiten 94-95 tut), dass der U, der oben definiert ist, hauptsächlich die μ-recursive Entsprechung von der universalen Maschine von Turing ist:

:To-KonstruktionsU soll die Definition einer allgemein-rekursiven Funktion U niederschreiben (n, x), der richtig die Nummer n interpretiert und rechnet, würde die passende Funktion x., um U zu bauen, direkt im Wesentlichen denselben Betrag der Anstrengung, und im Wesentlichen dieselben Ideen einschließen, wie wir ins Konstruieren der universalen Maschine von Turing investiert haben. (Kursive im Original, Minsky (1967) p. 189)

Symbolik

Mehrere verschiedene Symboliken werden in der Literatur verwendet. Ein Vorteil für das Verwenden der Symbolik ist eine Abstammung einer Funktion durch "das Nisten" der Maschinenbediener, die ein Inneres der andere leichter ist, in einer Kompaktform zu schreiben. Im folgenden werden wir die Reihe von Rahmen x..., x als x abkürzen:

• Unveränderliche Funktion: Gebrauch von Kleene "C (x) = q" und Boolos-Burgess-Jeffry (2002) (B-B-J) verwendet die Abkürzung "const (x) = n ":

:: z.B. C (r, s, t, u, v, w, x) = 13

:: z.B const (r, s, t, u, v, w, x) = 13

• Nachfolger-Funktion: Kleene verwendet x' und S für "den Nachfolger". Da, wie man betrachtet, "Nachfolger" primitiv ist, verwenden die meisten Texte den Apostroph wie folgt:

:: S (a) = ein +1 =', wo 1 = 0', 2 = 0 '', usw.

• Identitätsfunktion: Kleene (1952) Gebrauch "U", um die Identität anzuzeigen, fungieren über die Variablen x; B-B-J verwenden die Identitätsfunktion id über die Variablen x zu x:

: U (x) = id (x) = x

: z.B. U = id (r, s, t, u, v, w, x) = t

• Zusammensetzung (Ersatz) Maschinenbediener: Kleene verwendet eine Fettschrift S (um mit seinem S für "den Nachfolger" nicht verwirrt zu sein!). Der Exponent "m" bezieht sich auf die M der Funktion "f", wohingegen sich die Subschrift "n" auf die n Variable "x" bezieht:

:If wird uns h (x) = g (f (x)..., f (x)) gegeben

:: h (x) = S (g, f..., f)

:In schreibt eine ähnliche Weise, aber ohne sub - und Exponenten, B-B-J:

:: h (x') = Cn [g, f..., f] (x)

• Primitiver Recursion: Kleene verwendet das Symbol "R (Grundschritt, Induktionsschritt)", wo n die Zahl von Variablen, B-B-J Gebrauch "Pr (Grundschritt, Induktionsschritt) (x)" anzeigt. Gegeben:

:* Grundschritt: h (0, x) = f (x), und

:* Induktionsschritt: h (y+1, x) = g (y, h (x, y), x)

: Beispiel: primitive recursion Definition + b:

::* Grundschritt: f (0, a) = = U (ein)

::* Induktionsschritt: f (b', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c' = S (U (b, c,)

::: R {U (a), S [(U (b, c, a)] }\

::: Pr {U (a), S [(U (b, c, a)] }\

Beispiel: Kleene führt ein Beispiel dessen an, wie man die rekursive Abstammung von f durchführt (b, a) = b + (bemerken Sie Umkehrung von Variablen a und b). Er, mit 3 Initiale anfangend, fungiert

:# S (a) ='

:# U (a) = ein

:# U (b, c, a) = c

:# g (b, c, a) = S (U (b, c, a)) = c'

:# stützen Schritt: h (0, a) = U (ein)

:: Induktionsschritt: h (b', a) = g (b, h (b, a),)

Er erreicht:

:: a+b = R [U, S (S, U)]

Beispiele

• Fibonacci-Zahl
• McCarthy 91 Funktion

Siehe auch

• Theorie von Recursion
• Recursion
• Recursion (Informatik)

Links

• Enzyklopädie von Stanford des Philosophie-Zugangs
• Stephen Kleene (1952) Einführung in Metamathematics. Walters-Noordhoff & North-Holland, mit Korrekturen (6. Abdruck 1971); der zehnte Eindruck 1991, internationale Standardbuchnummer 0-7204-2103-9.
• Soare, R. Rekursiv Enumerable-Sätze und Grade. Springer-Verlag 1987.
• Marvin L. Minsky (1967), Berechnung: Begrenzte und unendliche Maschinen, Prentice-Hall, Inc. Englewood Klippen, N.J.

:On-Minsky der Seiten 210-215 zeigt, wie man den μ-operator mit dem Register-Maschinenmodell schafft, so seine Gleichwertigkeit zu den allgemeinen rekursiven Funktionen demonstrierend.

• George Boolos, John Burgess, Richard Jeffrey (2002), Berechenbarkeit und Logik: Die Vierte Ausgabe, Universität von Cambridge Presse, Cambridge, das Vereinigte Königreich. Vgl Seiten 70-71.