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 d' entiers naturels vers des entiers 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 ). En théorie de la calculabilité , il est démontré que les fonctions μ-récursives sont précisément les fonctions qui peuvent être calculées par les machines de Turing (c'est l'un des théorèmes qui soutiennent 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 d'Ackermann .

D'autres classes équivalentes de fonctions sont les fonctions du calcul lambda et les fonctions qui peuvent être calculées par les 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é informatique sous le nom de classe de complexité R.

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. Elles constituent 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 de minimisation μ .

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 être prouvée comme étant récursive totale et non primitive.

Fonctions primitives ou « de base » :

1. Fonctions constantes C^k
   _n:Pour chaque nombre naturel n et chaque k

   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 :

3. Fonction de projection (également appelée fonction d'identité ) : Pour tous les nombres naturels tels que :

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 pendant le calcul fournit un résultat bien défini) :

1. Opérateur de composition (également appelé opérateur de substitution ) : Étant donné une fonction m-aire et m fonctions k-aires :

   Cela signifie que est défini seulement si et sont tous définis.

2. Opérateur de récursivité primitif ρ : Étant données la fonction k -aire et la fonction k +2 -aire :

   Cela signifie que est défini uniquement si et sont définis pour tout

3. Opérateur de minimisation μ : Étant donnée une fonction ( k +1)-aire , la fonction k -aire est définie par :

   0\quad { ext{pour}}\quad i=0,\ldots ,z-1\quad { ext{et}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed05f72c426b147ff72e154987649de7855a176">

Intuitivement, la minimisation recherche – en commençant la recherche à partir de 0 et en progressant vers le haut – le plus petit argument qui amène la fonction à renvoyer 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 n'est pas définie pour l'argument

Alors que certains manuels utilisent l'opérateur μ tel que défini ici, d'autres comme exigent que l'opérateur μ soit appliqué uniquement aux fonctions totales f . 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 forme normale de Kleene (voir ci-dessous). La seule différence est qu'il devient indécidable qu'une définition de fonction spécifique définisse une fonction μ-récursive, comme il est indécidable qu'une fonction calculable (c'est-à-dire μ-récursive) soit totale.

La relation d'égalité forte peut être utilisée pour comparer des fonctions μ-récursives partielles. Elle est définie pour toutes les fonctions partielles f et g de telle sorte que

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.

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

Les exemples suivants sont uniquement destinés à 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.

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

Une fonction récursive générale est dite 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'existe aucun moyen de déterminer de manière calculable si une fonction récursive générale donnée est totale - voir Problème d'arrêt .

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 non borné 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).

Un théorème de forme normale dû à Kleene dit que pour chaque k il existe des fonctions récursives primitives et telles que pour toute fonction μ-récursive à k variables libres il existe un e tel que

Le nombre e est appelé indice ou nombre de Gödel pour la fonction f . 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 que ce qui est défini ci-dessus est en substance l'équivalent μ-récursif de la machine de Turing universelle :

Construire U revient à é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 celles que nous avons investies dans la construction de la machine de Turing universelle

Un certain nombre de symbolismes différents sont utilisés dans la littérature. L'un des avantages de l'utilisation du symbolisme est qu'une dérivation d'une fonction par « imbrication » 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 « successeur ». Comme « successeur » est considéré comme primitif, la plupart des textes utilisent l'apostrophe comme suit :

S(a) = a +1 = _déf a', où 1 = _déf 0', 2 = _déf 0 ' ', etc.

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

Tuⁿ
_je( x ) = identifiantⁿ
_je( x ) = x _i

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 variable "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ⁿ
_m(g, f ₁ , ... , f _m )

De la même manière, mais sans les indices et les exposants, BBJ écrit :

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

• Récursivité 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 ) ». Étant donné :

• étape 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 récursivité primitive de a + b :

• étape 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, a ))

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

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

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

1. S(a) = a'
2. Tu¹
   ₁(a) = un
3. Tu³
   ₂( b, c, a ) = c
4. g(b, c, a) = S(U³
   ₂( b, c, a )) = c'
5. étape 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³
₂) ]

• Nombre de Fibonacci
• Fonction McCarthy 91