Allgemeine rekursive Funktion - General recursive function

In der mathematischen Logik und Informatik ist eine allgemeine rekursive Funktion , partielle rekursive Funktion oder μ-rekursive Funktion eine Teilfunktion von natürlichen Zahlen zu natürlichen Zahlen, die in einem intuitiven Sinne "berechenbar" ist. Wenn die Funktion insgesamt ist, wird es auch eine gerufene Gesamt rekursive Funktion (manchmal verkürzt rekursive Funktion ). In der Berechenbarkeitstheorie wird gezeigt, dass die μ-rekursiven Funktionen genau die Funktionen sind, die von Turing-Maschinen berechnet werden können (dies ist einer der Sätze, die die Church-Turing-These stützen ). Die μ-rekursiven Funktionen sind eng mit primitiven rekursiven Funktionen verwandt , und ihre induktive Definition (unten) baut auf der der primitiven rekursiven Funktionen auf. Allerdings ist nicht jede totalrekursive Funktion eine primitive rekursive Funktion – das bekannteste Beispiel ist die Ackermann-Funktion .

Andere äquivalente Funktionsklassen sind die Funktionen der Lambda-Kalküle und die Funktionen, die durch Markov-Algorithmen berechnet werden können .

Die Teilmenge aller total rekursiven Funktionen mit Werten in {0,1} ist in der rechnerischen Komplexitätstheorie als Komplexitätsklasse R bekannt .

Definition

Die μ-rekursiven Funktionen (oder allgemeine rekursive Funktionen ) sind Teilfunktionen, die endliche Tupel natürlicher Zahlen nehmen und eine einzelne natürliche Zahl zurückgeben. Sie sind die kleinste Klasse von Partialfunktionen, die die Anfangsfunktionen enthält und unter Komposition, primitiver Rekursion und dem μ-Operator abgeschlossen ist .

Die kleinste Klasse von Funktionen einschließlich der Anfangsfunktionen und abgeschlossen unter Komposition und primitiver Rekursion (dh ohne Minimierung) ist die Klasse der primitiven rekursiven Funktionen . Während alle primitiven rekursiven Funktionen total sind, gilt dies nicht für partielle rekursive Funktionen; beispielsweise ist die Minimierung der Nachfolgefunktion undefiniert. Die primitiven rekursiven Funktionen sind eine Teilmenge der totalen rekursiven Funktionen, die eine Teilmenge der partiellen rekursiven Funktionen sind. Zum Beispiel kann die Ackermann-Funktion als total rekursiv und als nicht-primitiv bewiesen werden.

Primitive oder "grundlegende" Funktionen:

1. Konstante Funktionen C^k
   _n: Für jede natürliche Zahl und jede Alternative verwenden Definitionen stattdessen eine Nullfunktion als primitive Funktion, die immer Null zurückgibt, und baut die konstanten Funktionen aus der Nullfunktion, der Nachfolgerfunktion und dem Kompositionsoperator auf.${\displaystyle n\,}$${\displaystyle k\,}$
       ${\displaystyle C_{n}^{k}(x_{1},\ldots,x_{k}){\stackrel {\mathrm {def} }{=}}n}$
   
2. Nachfolgefunktion S:
       ${\displaystyle S(x){\stackrel {\mathrm {def} }{=}}x+1\,}$
3. Projektionsfunktion (auch Identitätsfunktion genannt ): Für alle natürlichen Zahlen, so dass :${\displaystyle P_{i}^{k}}$${\displaystyle i,k}$${\displaystyle 1\leq i\leq k}$
       ${\displaystyle P_{i}^{k}(x_{1},\ldots,x_{k}){\stackrel {\mathrm {def} }{=}}x_{i}\,.}$

Operatoren (der durch einen Operator definierte Bereich einer Funktion ist die Menge der Werte der Argumente, so dass jede Funktionsanwendung, die während der Berechnung durchgeführt werden muss, ein wohldefiniertes Ergebnis liefert):

1. Kompositionsoperator (auch Substitutionsoperator genannt ): Gegeben eine m-äre Funktion und m k-äre Funktionen : Dies bedeutet, dass nur definiert ist, wenn und alle definiert sind.${\displaystyle \circ\,}$${\displaystyle h(x_{1},\ldots,x_{m})\,}$${\displaystyle g_{1}(x_{1},\ldots,x_{k}),\ldots,g_{m}(x_{1},\ldots,x_{k})}$
       ${\displaystyle h\circ(g_{1},\ldots,g_{m}){\stackrel {\mathrm {def} }{=}}f,\quad {\text{wo}}\quad f(x_ {1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots , x_{k})).}$
   ${\displaystyle f(x_{1},\ldots,x_{k})}$${\displaystyle g_{1}(x_{1},\ldots,x_{k}),\ldots,g_{m}(x_{1},\ldots,x_{k}),}$${\displaystyle h(g_{1}(x_{1},\ldots,x_{k}),\ldots,g_{m}(x_{1},\ldots,x_{k}))}$
2. Primitiver Rekursionsoperator : Gegeben die k -äre Funktion und k +2 -äre Funktion : Dies bedeutet, dass nur definiert ist, wenn und für alle definiert sind${\displaystyle \rho\,}$${\displaystyle g(x_{1},\ldots,x_{k})\,}$${\displaystyle h(y,z,x_{1},\ldots,x_{k})\,}$
       ${\displaystyle {\begin{ausgerichtet}\rho (g,h)&{\stackrel {\mathrm {def} }{=}}f\quad {\text{wobei die k+1 -äre Funktion }}f{ \text{ ist definiert durch}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S( y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{ k})\,.\end{ausgerichtet}}}$
   ${\displaystyle f(y,x_{1},\ldots,x_{k})}$${\displaystyle g(x_{1},\ldots,x_{k})}$${\displaystyle h(z,f(z,x_{1},\ldots,x_{k}),x_{1},\ldots,x_{k})}$${\displaystyle z<y.}$
3. Minimierungsoperator : Bei einer gegebenen ( k +1)-ären Funktion ist die k- äre Funktion definiert durch: Intuitiv sucht die Minimierung – beginnend mit der Suche bei 0 und fortschreitend – das kleinste Argument, das bewirkt, dass die Funktion Null zurückgibt ; wenn es kein solches Argument gibt oder wenn man auf ein Argument trifft, für das f nicht definiert ist, dann endet die Suche nie und ist für das Argument nicht definiert ( Hinweis : Während einige Lehrbücher den μ-Operator wie hier definiert verwenden, verwenden andere wie fordern, dass der μ-Operator nur auf totale Funktionen angewendet wird . Obwohl dies den μ-Operator gegenüber der hier gegebenen Definition einschränkt, bleibt die Klasse der μ-rekursiven Funktionen die gleiche, was aus Kleenes Normalformsatz folgt (siehe unten ). Der einzige Unterschied besteht darin, dass es unentscheidbar wird, ob eine bestimmte Funktionsdefinition eine μ-rekursive Funktion definiert, da es unentscheidbar ist, ob eine berechenbare (dh μ-rekursive) Funktion total ist.)${\displaystyle \mu\,}$${\displaystyle f(y,x_{1},\ldots,x_{k})\,}$${\displaystyle \mu(f)}$
       ${\displaystyle {\begin{ausgerichtet}\mu(f)(x_{1},\ldots,x_{k})=z{\stackrel {\mathrm {def} }{\iff}}\ f(i, x_{1},\ldots ,x_{k})&>0\quad {\text{für}}\quad i=0,\ldots ,z-1\quad {\text{und}}\\f( z,x_{1},\ldots,x_{k})&=0\quad\end{ausgerichtet}}}$
   ${\displaystyle \mu(f)}$${\displaystyle (x_{1},\ldots,x_{k}).}$
   ${\displaystyle f}$

Der starke Gleichheit Operator kann verwendet werden , teilweise μ-rekursiven Funktionen zu vergleichen. Dies ist für alle Teilfunktionen f und g so definiert, dass ${\displaystyle\simeq}$

${\displaystyle f(x_{1},\ldots,x_{k})\simeq g(x_{1},\ldots,x_{l})}$

gilt genau dann, wenn für eine beliebige Auswahl von Argumenten entweder beide Funktionen definiert und ihre Werte gleich sind oder beide Funktionen undefiniert sind.

Total rekursive Funktion

Eine allgemeine rekursive Funktion heißt totalrekursive Funktion, wenn sie für jede Eingabe definiert ist oder äquivalent von einer totalen Turingmaschine berechnet werden kann . Es gibt keine Möglichkeit, berechenbar zu sagen, ob eine gegebene allgemeine rekursive Funktion total ist – siehe Halteproblem .

Äquivalenz mit anderen Berechenbarkeitsmodellen

Bei der Äquivalenz von Berechenbarkeitsmodellen wird eine Parallele zwischen Turingmaschinen , die für bestimmte Eingaben nicht terminieren, und einem undefinierten Ergebnis für diese Eingabe in der entsprechenden partiellen rekursiven Funktion gezogen. Der unbegrenzte Suchoperator ist durch die Regeln der primitiven Rekursion nicht definierbar, da diese keinen Mechanismus für "unendliche Schleifen" (undefinierte Werte) bieten.

Normalformsatz

Ein Normalformsatz von Kleene besagt, dass es für jedes k primitive rekursive Funktionen gibt und für jede μ-rekursive Funktion mit k freien Variablen ein e mit ${\displaystyle U(y)\!}$${\displaystyle T(y,e,x_{1},\ldots,x_{k})\!}$${\displaystyle f(x_{1},\ldots,x_{k})\!}$

${\displaystyle f(x_{1},\ldots,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots,x_{k}))}$.

Die Zahl e wird Index- oder Gödelzahl für die Funktion f genannt . Eine Folge dieses Ergebnisses ist, dass jede μ-rekursive Funktion unter Verwendung einer einzigen Instanz des μ-Operators definiert werden kann, der auf eine (gesamte) primitive rekursive Funktion angewendet wird.

Minsky beobachtet, dass das oben definierte im Wesentlichen das μ-rekursive Äquivalent der universellen Turingmaschine ist : ${\displaystyle U}$

U zu konstruieren bedeutet, die Definition einer allgemein-rekursiven Funktion U(n, x) aufzuschreiben, die die Zahl n richtig interpretiert und die entsprechende Funktion von x berechnet. U direkt zu konstruieren würde im Wesentlichen den gleichen Aufwand und im Wesentlichen die gleichen Ideen erfordern, die wir in den Bau der universellen Turingmaschine investiert haben

Symbolismus

In der Literatur werden verschiedene Symboliken verwendet. Ein Vorteil bei der Verwendung der Symbolik ist, dass eine Ableitung einer Funktion durch "Verschachtelung" der Operatoren ineinander einfacher in kompakter Form geschrieben werden kann. Im Folgenden kürzen wir die Parameterkette x ₁ , ..., x _n mit x ab :

• Konstante Funktion : Kleene verwendet "Cⁿ
  _q( x ) = q " und Boolos-Burgess-Jeffrey (2002) (BBJ) verwenden die Abkürzung " const _n ( x ) = n ":

zB C⁷
₁₃ ( r, s, t, u, v, w, x ) = 13

zB const ₁₃ ( r, s, t, u, v, w, x ) = 13

• Nachfolgerfunktion : Kleene verwendet x' und S für "Nachfolger". Da "Nachfolger" als primitiv gilt, verwenden die meisten Texte den Apostroph wie folgt:

S(a) = a +1 = _def a', wobei 1 = _def 0', 2 = _def 0 ' ' usw.

• Identitätsfunktion : Kleene (1952) verwendet "Uⁿ
  _ich" um die Identitätsfunktion über den Variablen x _i anzuzeigen ; BBJ verwenden die Identitätsfunktion idⁿ
  _ichüber die Variablen x ₁ bis x _n :

Uⁿ
_ich( x ) = idⁿ
_ich( x ) = x _i

zB U⁷
₃ = id⁷
₃ ( r, s, t, u, v, w, x ) = t

• Kompositions-(Substitutions-)Operator : Kleene verwendet ein fett gedrucktes S^m
  _n(nicht zu verwechseln mit seinem S für "Nachfolger" ! ). Das hochgestellte "m" bezieht sich auf die m- ^te der Funktion "f _m ", während sich die tiefgestellte "n" auf die n- ^te Variable "x _n " bezieht :

Ist h( x )= g( f ₁ ( x ), ... , f _m ( x ) ) gegeben

h( x ) = Sⁿ
_m(g, f ₁ , ... , f _m )

Auf ähnliche Weise, aber ohne die tiefgestellten und hochgestellten Zeichen, schreiben BBJ:

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

• Primitive Rekursion : Kleene verwendet das Symbol " R ⁿ (Basisschritt, Induktionsschritt) " wobei n die Anzahl der Variablen angibt, BBJ verwendet " Pr (Basisschritt, Induktionsschritt) ( x )". Gegeben:

• Basisschritt: h( 0, x )= f( x ), und
• Induktionsschritt: h( y+1, x ) = g( y, h(y, x ), x )

Beispiel: primitive Rekursionsdefinition von a + b:

• Basisschritt: f( 0, a ) = 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, a))

R ² { U¹
₁(a), S [ (U³
₂( b, c, a ) ] }

Pr{ U¹
₁(a), S[ (U³
₂( b, c, a ) ] }

Beispiel : Kleene gibt ein Beispiel für die rekursive Ableitung von f(b, a) = b + a (beachte die Umkehrung der Variablen a und b). Er beginnt mit 3 Anfangsfunktionen

1. S(a) = a'
2. U¹
   ₁(a) = a
3. U³
   ₂( b, c, a ) = c
4. g(b, c, a) = S(U³
   ₂(b, c, a)) = c'
5. Basisschritt: h( 0, a ) = U¹
   ₁(ein)

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

Er kommt an:

a + b = R ² [U¹
₁, S³
₁(S, U³
₂) ]

Beispiele

• Fibonacci-Zahl
• McCarthy 91-Funktion

Siehe auch

• Rekursionstheorie
• Rekursion
• Rekursion (Informatik)

Verweise

Externe Links

• Eintrag zur Stanford Encyclopedia of Philosophy
• Ein Compiler zum Umwandeln einer rekursiven Funktion in eine äquivalente Turingmaschine