Fonction récursive générale

En logique mathématique et en informatique , une fonction récursive générale , une fonction récursive partielle ou une fonction μ-récursive est une fonction partielle des nombres naturels aux nombres naturels qui est “calculable” dans un sens intuitif – ainsi que dans un sens formel . Si la fonction est totale, elle est également appelée fonction récursive totale (parfois abrégée en fonction récursive ). ^[1] En théorie de la calculabilité , on montre que les fonctions μ-récursives sont précisément les fonctions qui peuvent être calculées par les machines de Turing^{[2] [4]} (c’est l’un des théorèmes qui soutient La thèse de Church-Turing ). Les fonctions μ-récursives sont étroitement liées aux Fonctions récursives primitives , et leur définition inductive (ci-dessous) s’appuie sur celle des Fonctions récursives primitives. Cependant, toutes les fonctions récursives totales ne sont pas des Fonctions récursives primitives – l’exemple le plus célèbre est la fonction Ackermann .

D’autres classes équivalentes de fonctions sont les fonctions du calcul lambda et les fonctions qui peuvent être calculées par des algorithmes de Markov .

Le sous-ensemble de toutes les fonctions récursives totales avec des valeurs dans {0,1} est connu dans la théorie de la complexité computationnelle sous le nom de classe de complexité R .

Définition

Les fonctions μ-récursives (ou fonctions récursives générales ) sont des fonctions partielles qui prennent des tuples finis de nombres naturels et renvoient un seul nombre naturel. Il s’agit de la plus petite classe de fonctions partielles qui inclut les fonctions initiales et est fermée par la composition, la récursivité primitive et l’ opérateur μ .

La plus petite classe de fonctions comprenant les fonctions initiales et fermées par composition et récursivité primitive (c’est-à-dire sans minimisation) est la classe des Fonctions récursives primitives . Alors que toutes les Fonctions récursives primitives sont totales, ce n’est pas le cas des fonctions récursives partielles; par exemple, la minimisation de la fonction successeur n’est pas définie. Les Fonctions récursives primitives sont un sous-ensemble des fonctions récursives totales, qui sont un sous-ensemble des fonctions récursives partielles. Par exemple, la fonction d’Ackermann peut s’avérer totalement récursive et non primitive.

Fonctions primitives ou “de base”:

1. Fonctions constantes C^k
   _n: Pour tout entier naturel n et tout k C n k ( X 1 , … , X k ) = ré e F n {displaystyle C_{n}^{k}(x_{1},ldots ,x_{k}) {stackrel {mathrm {def} }{=}} n} Les définitions alternatives utilisent à la place une fonction zéro comme fonction primitive qui renvoie toujours zéro, et construisent les fonctions constantes à partir de la fonction zéro, de la fonction successeur et de l’opérateur de composition.
2. Fonction successeur S : S ( x ) = d e f x + 1 {displaystyle S(x) {stackrel {mathrm {def} }{=}} x+1,}
3. Fonction projection P i k {displaystyle P_{i}^{k}} (également appelée fonction d’identité ) : pour tous les nombres naturels i , k {displaystyle i,k} tel que 1 ≤ i ≤ k {displaystyle 1leq ileq k} : P i k ( x 1 , … , x k ) = d e f x i . {displaystyle P_{i}^{k}(x_{1},ldots ,x_{k}) {stackrel {mathrm {def} }{=}} x_{i},.}

Opérateurs (le domaine d’une fonction défini par un opérateur est l’ensemble des valeurs des arguments tels que chaque application de fonction qui doit être faite lors du calcul fournit un résultat bien défini) :

1. Opérateur de composition ∘ {displaystyle circ ,} (également appelé opérateur de substitution ) : étant donné une fonction m-aire h ( x 1 , … , x m ) {displaystyle h(x_{1},ldots ,x_{m}),} et m fonctions k-aires g 1 ( x 1 , … , x k ) , … , g m ( x 1 , … , x k ) {displaystyle g_{1}(x_{1},ldots ,x_{k}),ldots ,g_{m}(x_{1},ldots ,x_{k})} : h ∘ ( g 1 , … , g m ) = d e f f , where f ( x 1 , … , x k ) = h ( g 1 ( x 1 , … , x k ) , … , g m ( x 1 , … , x k ) ) . {displaystyle hcirc (g_{1},ldots ,g_{m}) {stackrel {mathrm {def} }{=}} f,quad {text{where}}quad f (x_{1},ldots ,x_{k})=h(g_{1}(x_{1},ldots ,x_{k}),ldots ,g_{m}(x_{1}, ldots ,x_{k})).} Cela signifie que f ( x 1 , … , x k ) {displaystyle f(x_{1},ldots ,x_{k})} n’est défini que si g 1 ( x 1 , … , x k ) , … , g m ( x 1 , … , x k ) , {displaystyle g_{1}(x_{1},ldots ,x_{k}),ldots ,g_{m}(x_{1},ldots ,x_{k}),} et h ( g 1 ( X 1 , … , X k ) , … , g m ( x 1 , … , x k ) ) {displaystyle h(g_{1}(x_{1},ldots ,x_{k}),ldots ,g_{m}(x_{1},ldots ,x_{k}))} sont tous définis.
2. Opérateur de récurrence primitif ρ : Étant donné la fonction k -aire g ( x 1 , … , x k ) {displaystyle g(x_{1},ldots ,x_{k}),} et fonction k +2 -aire h ( y , z , x 1 , … , x k ) {displaystyle h(y,z,x_{1},ldots ,x_{k}),} : ρ ( g , h ) = d e f f where the k+1 -ary function f is defined by f ( 0 , x 1 , … , x k ) = g ( x 1 , … , x k ) f ( S ( y ) , x 1 , … , x k ) = h ( y , f ( y , x 1 , … , x k ) , x 1 , … , x k ) . {displaystyle {begin{aligned}rho (g,h)& {stackrel {mathrm {def} }{=}} fquad {text{où la fonction k+1 -aire}} f{text{ est défini par}}\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{aligné}}} Cela signifie que f ( y , x 1 , … , x k ) {displaystyle f(y,x_{1},ldots ,x_{k})} n’est défini que si g ( x 1 , … , x k ) {displaystyle g(x_{1},ldots ,x_{k})} et h ( z , f ( z , x 1 , … , x k ) , x 1 , … , x k ) {displaystyle h(z,f(z,x_{1},ldots ,x_{k}),x_{1},ldots ,x_{k})} sont définis pour tous z < y . {displaystyle z<y.}
3. Opérateur de minimisation μ : Soit une fonction ( k +1)-aire f ( y , x 1 , … , x k ) {displaystyle f(y,x_{1},ldots ,x_{k}),} , la fonction k -aire μ ( f ) {displaystylemu (f)} est défini par : μ ( f ) ( x 1 , … , x k ) = z ⟺ d e f f ( i , x 1 , … , X k ) > 0 pour i = 0 , … , z − 1 and f ( z , x 1 , … , x k ) = 0 {displaystyle {begin{aligned}mu (f)(x_{1},ldots ,x_{k})=z{stackrel {mathrm {def} }{iff }} f(i, x_{1},ldots ,x_{k})&>0quad {text{for}}quad i=0,ldots ,z-1quad {text{and}}\f( z,x_{1},ldots ,x_{k})&=0quad end{aligned}}}

Intuitivement, la minimisation cherche – en commençant la recherche à partir de 0 et en remontant – le plus petit argument qui fait que la fonction renvoie zéro ; s’il n’y a pas un tel argument, ou si l’on rencontre un argument pour lequel f n’est pas défini, alors la recherche ne se termine jamais, et μ ( f ) {displaystylemu (f)} n’est pas défini pour l’argument ( x 1 , … , x k ) . {displaystyle (x_{1},ldots ,x_{k}).}

Alors que certains manuels utilisent l’opérateur μ tel que défini ici, ^{[5] [6]} d’autres comme ^{[7] [8]} exigent que l’opérateur μ soit appliqué aux fonctions totales f uniquement. Bien que cela limite l’opérateur μ par rapport à la définition donnée ici, la classe des fonctions μ-récursives reste la même, ce qui découle du théorème de la forme normale de Kleene (voir ci- dessous ). ^{[5] [6]} La seule différence est qu’il devient indécidable si une définition de fonction spécifique définit une fonction μ-récursive, car il est indécidable si une fonction calculable (c’est-à-dire μ-récursive) est totale. ^[7]

L’ opérateur d’égalité forte ≃ {displaystylesimeq} peut être utilisé pour comparer des fonctions μ-récursives partielles. Ceci est défini pour toutes les fonctions partielles f et g de sorte que

f ( x 1 , … , x k ) ≃ g ( x 1 , … , x l ) {displaystyle f(x_{1},ldots ,x_{k})simeq g(x_{1},ldots ,x_{l})}

est valable si et seulement si pour tout choix d’arguments, soit les deux fonctions sont définies et leurs valeurs sont égales, soit les deux fonctions ne sont pas définies.

Exemples

Des exemples n’impliquant pas l’opérateur de minimisation peuvent être trouvés dans Fonction récursive primitive#Examples .

Les exemples suivants sont destinés uniquement à démontrer l’utilisation de l’opérateur de minimisation ; ils pourraient également être définis sans lui, bien que de manière plus compliquée, car ils sont tous récursifs primitifs.

• La racine carrée entière de x {style d’affichage x} peut être défini comme le moins z {displaystyle z} tel que ( z + 1 ) 2 > x {displaystyle (z+1)^{2}>x} . En utilisant l’opérateur de minimisation, une définition récursive générale est I s q r t = μ ( N o t ∘ G t ∘ ( M u l ∘ ( S ∘ P 1 2 , S ∘ P 1 2 ) , P 2 2 ) ) {displaystyle Isqrt=mu (Notcirc Gtcirc (Mulcirc (Scirc P_{1}^{2},Scirc P_{1}^{2}),P_{2}^{ 2}))} , où N o t {displaystyle Non} , G t {displaystyle GT} , et M u l {displaystyle Mul} sont respectivement la négation logique, le supérieur à et la multiplication ^[9] . En réalité, ( N o t ∘ G t ∘ ( M u l ∘ ( S ∘ P 1 2 , S ∘ P 1 2 ) , P 2 2 ) ) ( z , x ) = ( ¬ S ( z ) ∗ S ( z ) > x ) {displaystyle (Notcirc Gtcirc (Mulcirc (Scirc P_{1}^{2},Scirc P_{1}^{2}),P_{2}^{2})) ;(z,x)=(lpas S(z)*S(z)>x)} est 0 {displaystyle 0} si et seulement si, S ( z ) ∗ S ( z ) > x {displaystyle S(z)*S(z)>x} tient. Ainsi I s q r t ( x ) {displaystyle isqrt(x)} est le moins z {displaystyle z} tel que S ( z ) ∗ S ( z ) > x {displaystyle S(z)*S(z)>x} tient. Le joncteur de négation N o t {displaystyle Non} est nécessaire depuis G t {displaystyle GT} encode la vérité par 1 {displaystyle 1} , pendant que μ {displaystylemu} cherche pour 0 {displaystyle 0} .

Les exemples suivants définissent des fonctions récursives générales qui ne sont pas récursives primitives ; par conséquent, ils ne peuvent pas éviter d’utiliser l’opérateur de minimisation.

• ^{[ exemple nécessaire ]}

Fonction récursive totale

Une fonction récursive générale est appelée fonction récursive totale si elle est définie pour chaque entrée, ou, de manière équivalente, si elle peut être calculée par une Machine de Turing totale . Il n’y a aucun moyen de savoir de manière informatique si une fonction récursive générale donnée est totale – voir Problème d’arrêt .

Équivalence avec d’autres modèles de calculabilité

Apprendre encore plus Cette section a besoin d’être agrandie . Vous pouvez aider en y ajoutant . ( février 2010 )

Dans l’ équivalence des modèles de calculabilité , un parallèle est établi entre les machines de Turing qui ne se terminent pas pour certaines entrées et un résultat indéfini pour cette entrée dans la fonction récursive partielle correspondante. L’opérateur de recherche illimité n’est pas définissable par les règles de récursivité primitive car celles-ci ne fournissent pas de mécanisme pour les “boucles infinies” (valeurs indéfinies).

Théorème de la forme normale

Un théorème de forme normale dû à Kleene dit que pour chaque k il existe des Fonctions récursives primitives U ( y ) {displaystyle U(y)!} et T ( y , e , x 1 , … , x k ) {displaystyle T(y,e,x_{1},ldots ,x_{k})!} tel que pour toute fonction μ-récursive f ( x 1 , … , x k ) {displaystyle f(x_{1},ldots ,x_{k})!} avec k variables libres il existe un e tel que

f ( x 1 , … , x k ) ≃ U ( μ y T ( y , e , x 1 , … , x k ) ) {displaystyle f(x_{1},ldots ,x_{k})simeq U(mu y,T(y,e,x_{1},ldots ,x_{k}))} .

Le nombre e est appelé indice ou nombre de Gödel pour la fonction f . ^{[10] : 52–53} Une conséquence de ce résultat est que toute fonction μ-récursive peut être définie en utilisant une seule instance de l’opérateur μ appliqué à une fonction récursive primitive (totale).

Minsky observe U {displaystyle U} défini ci-dessus est essentiellement l’équivalent μ-récursif de la machine de Turing universelle :

Construire U, c’est écrire la définition d’une fonction récursive générale U(n, x) qui interprète correctement le nombre n et calcule la fonction appropriée de x. construire U directement impliquerait essentiellement la même quantité d’efforts, et essentiellement les mêmes idées , que nous avons investi dans la construction de la machine de Turing universelle ^[11]

Symbolisme

Un certain nombre de symboles différents sont utilisés dans la littérature. Un avantage à utiliser le symbolisme est qu’une dérivation d’une fonction par “emboîtement” des opérateurs les uns dans les autres est plus facile à écrire sous une forme compacte. Dans ce qui suit, la chaîne de paramètres x ₁ , …, x _n est abrégée en x :

• Fonction constante : Kleene utilise ” Cⁿ
  _q( x ) = q ” et Boolos-Burgess-Jeffrey (2002) (BBJ) utilisent l’abréviation ” const _n ( x ) = n ” :

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

• Fonction successeur : Kleene utilise x’ et S pour “Successor”. Comme « successeur » est considéré comme primitif, la plupart des textes utilisent l’apostrophe comme suit :

S(a) = a +1 = _def a’, où 1 = _def 0′, 2 = _def 0 ‘ ‘, etc.

• Fonction d’identité : Kleene (1952) utilise ” Uⁿ
  _je” pour indiquer la fonction identité sur les variables x _i ; BBJ utilise la fonction identité idⁿ
  _jesur les variables x ₁ à x _n :

tu ⁿ
_je( x ) = identifiant ⁿ
_je( X ) = X _je par exemple U ⁷
₃= identifiant ⁷
₃( r, s, t, u, v, w, x ) = t

• Opérateur de composition (substitution) : Kleene utilise un S en gras^m
  _n(à ne pas confondre avec son S pour “successeur” ! ). L’exposant « m » fait référence à la m ^ième de la fonction « f _m », tandis que l’indice « n » fait référence à la n ^ième variable « x _n » :

Si on nous donne h( x )= g( f ₁ ( x ), … , f _m ( x ) ) h( x ) = S ^nm
_{_}(g, f ₁ , … , f _m ) De la même manière, mais sans les indices et exposants, BBJ écrit : h( x’ )= Cn[g, f ₁ ,…, f _m ]( x )

• Récursion primitive : Kleene utilise le symbole ” R ⁿ (étape de base, étape d’induction) ” où n indique le nombre de variables, BBJ utilise ” Pr(étape de base, étape d’induction)( x )”. Donné:

• pas de base : h( 0, x )= f( x ), et
• étape d’induction : h( y+1, x ) = g( y, h(y, x ), x )

Exemple : définition de la récursivité primitive de a + b :

• pas de base : f( 0, a ) = a = U¹
  ₁(un)
• étape d’induction : f( b’ , a ) = ( f ( b, a ) )’ = g( b, f( b, a), a ) = g( b, c, a ) = c’ = S(U³
  ₂( b, c, une ))

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

Exemple : Kleene donne un exemple de comment effectuer la dérivation récursive de f(b, a) = b + a (notez l’inversion des variables a et b). Il commence par 3 fonctions initiales

1. S(a) = a’
2. tu¹
   ₁(a) = un
3. tu³
   ₂( b, c, une ) = c
4. g(b, c, a) = S(U³
   ₂( b, c, une )) = c’
5. pas de base : h( 0, a ) = U¹
   ₁(un)

étape d’induction : h( b’, a ) = g( b, h( b, a ), a )

Il arrive à :

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

Exemples

• Nombre de Fibonacci
• Fonction McCarthy 91

Voir également

• Théorie de la récursivité
• Récursivité
• Récursivité (informatique)

Références

1. ^ “Fonctions récursives” . L’Encyclopédie de Philosophie de Stanford . Laboratoire de recherche en métaphysique, Université de Stanford. 2021.
2. ^ Stanford Encyclopedia of Philosophy , Entry Recursive Functions , Sect.1.7: “[La classe des fonctions μ-récursives] s’avère coïncider avec la classe des fonctions calculables de Turing introduites par Alan Turing ainsi qu’avec la classe des λ -fonctions définissables introduites par Alonzo Church. ”
3. ^ Kleene, Stephen C. (1936). “λ-définissabilité et récursivité” . Journal mathématique du duc . 2 (2): 340–352. doi : 10.1215/s0012-7094-36-00227-2 .
4. ^ Turing, Alan Mathison (décembre 1937). “Calculabilité et λ-définissabilité”. Journal de logique symbolique . 2 (4): 153–163. doi : 10.2307/2268280 . JSTOR 2268280 . Aperçu de la preuve à la p.153 : λ -definable {displaystyle lambda {mbox{-définissable}}} ⟹ t r i v {displaystyle {stackrel {triv}{implique}}} λ – K -definable {displaystyle lambda {mbox{-}}K{mbox{-definable}}} ⟹ 160 {displaystyle {stackrel {160}{implique}}} Turing computable {displaystyle {mbox{Turing calculable}}} ⟹ 161 {displaystyle {stackrel {161}{implique}}} μ -recursive {displaystyle mu {mbox{-récursif}}} ⟹ K l e e n e {displaystyle {stackrel {Kleene}{implique}}} ^[3] λ -definable {displaystyle lambda {mbox{-définissable}}}
5. ^ ^{un b} Enderton, HB, Une introduction mathématique à la logique, Academic Press, 1972
6. ^ ^{un b} Boolos, GS, Burgess, JP, Jeffrey, RC, calculabilité et logique, Cambridge University Press, 2007
7. ^ ^{a b} Jones, ND, Calculabilité et complexité: d’une perspective de programmation, The MIT Press, Cambridge, Massachusetts, Londres, Angleterre, 1997
8. ^ Kfoury, AJ, RN Moll et MA Arbib, Une approche de programmation de la calculabilité, 2e éd., Springer-Verlag, Berlin, Heidelberg, New York, 1982
9. ^ défini dans Fonction récursive primitive # Juncteurs , Fonction récursive primitive # Prédicat d’ égalité et Fonction récursive primitive # Multiplication
10. ^ Stephen Cole Kleene (janvier 1943). “Prédicats et quantificateurs récursifs” (PDF) . Transactions de l’American Mathematical Society . 53 (1): 41–73. doi : 10.1090/S0002-9947-1943-0007371-8 .
11. ^ Minsky 1972 , p. 189.

• Kleene, Stephen (1991) [1952]. Introduction aux métamathématiques . Walters-Noordhoff & Nord-Hollande. ISBN 0-7204-2103-9.
• Soare, R. (1999) [1987]. Ensembles et degrés récursivement énumérables : une étude des fonctions calculables et des ensembles générés par calcul . Springer Verlag. ISBN 9783540152996.
• Minsky, Marvin L. (1972) [1967]. Calcul : machines finies et infinies . Prentice Hall. p. 210–5. ISBN 9780131654495.

Aux pages 210-215, Minsky montre comment créer l’opérateur μ en utilisant le modèle de machine de registre , démontrant ainsi son équivalence aux fonctions récursives générales.

• Boolos, George ; Burgess, John ; Jeffrey, Richard (2002). “6.2 Minimisation” . Calculabilité et logique (4e éd.). La presse de l’Universite de Cambridge. p. 70–71. ISBN 9780521007580.

Liens externes

• Entrée de l’Encyclopédie de philosophie de Stanford
• Un compilateur pour transformer une fonction récursive en une machine de Turing équivalente