Fonction récursive générale

En logique mathématique et en informatique , une fonction récursive générale , également appelée fonction récursive partielle ou fonction μ-récursive , est une fonction partielle des nombres naturels vers les nombres naturels qui est « calculable » au sens intuitif comme au sens formel . Si la fonction est totale , on l'appelle aussi fonction récursive totale (parfois abrégée en fonction récursive ). En théorie de la calculabilité , il a été démontré que les fonctions μ-récursives sont précisément les fonctions calculables 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, toute fonction récursive totale n'est pas une fonction récursive primitive ; l'exemple le plus connu est la fonction d'Ackermann .

D’autres classes de fonctions équivalentes sont les fonctions du lambda-calcul 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 la théorie de la complexité computationnelle sous le nom de classe de complexité R.

Fonctions primitives ou « basiques » :

1. Fonctions constantes
   D'autres définitions utilisent 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 identité ) : Pour tout nombre naturel tel que :

Opérateurs (le domaine d'une fonction définie par un opérateur est l'ensemble des valeurs des arguments telles que chaque application de fonction effectuée lors du calcul fournisse 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 uniquement si et sont tous définis.

2. Opérateur de récursion primitive

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

3. Opérateur de minimisation

   0 \\quad \ ext{for}\\quad i=0, \\ldots, z-1 \\quad\ ext{and}\\\\ f(z, x_1, \\ldots, x_k)&=0\\quad \\end{align}" 0\quad { ext{pour}}\quad i=0,\ldots ,z-1\quad { ext{et}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned

Intuitivement, la minimisation cherche, en partant de 0 et en remontant, le plus petit argument qui annule la fonction ; s’il n’existe pas d’argument de ce type, ou si l’on rencontre un argument pour lequel

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

Cela se vérifie 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 la section Fonction récursive primitive#Exemples .

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

racine carrée entière de x peut être définie comme le plus petit z tel que . En utilisant l'opérateur de minimisation, une définition récursive générale est , où Not , Gt et Mul sont respectivement la négation logique , le signe supérieur à et la multiplication . En fait, est x" $x(z+1{)}^2>x$x x)" $x)(\mathrm{Not}\circ \mathrm{Gt}\circ (\mathrm{Mul}\circ (S\circ P_1^2,S\circ P_1^2),P_2^2\left)\right)(z,x)=\left(\neg S\right(z)\ast S(z)>x)$x) 0 si, et seulement si, est vrai. Par conséquent, est le plus petit z tel que soit vrai. Le conjonction de négation Not est nécessaire puisque Gt encode la vérité par x" $xS\left(z\right)\ast S\left(z\right)>x$x x" $xS\left(z\right)\ast S\left(z\right)>x$x 1 , tandis que μ recherche0 .

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 éviter d'utiliser l'opérateur de minimisation.

Une fonction récursive générale est dite totale si elle est définie pour toute 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 par le calcul si une fonction récursive générale donnée est totale — voir le problème de l'arrêt .

Un théorème de forme normale dû à Kleene affirme 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é un indice ou un 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 l' ensemble défini ci-dessus est en substance l'équivalent μ-récursif de la machine de Turing universelle :

Construire U consiste à é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 le même effort et les mêmes idées que ceux que nous avons investis dans la construction de la machine de Turing universelle

Plusieurs symbolismes différents sont utilisés dans la littérature. L'un des avantages de l'utilisation de ces symbolismes est qu'il est plus facile d'écrire la dérivation d'une fonction par « imbrication » des opérateurs les uns dans les autres sous une forme compacte. Dans ce qui suit, la chaîne de paramètres est abrégée comme suit :

• Fonction constante : Kleene utilise " " et Boolos-Burgess-Jeffrey (2002) (BBJ) utilise l'abréviation " " :

par exemple

par exemple

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

, où

,

, etc.

• Fonction identité : Kleene (1952) l'utilise pour désigner la fonction identité sur les variables ; BBJ utilise la fonction identité sur les variables pour :

par exemple

• Opérateur de composition (substitution) : Kleene utilise le gras (à ne pas confondre avec son utilisation du terme « successeur » !). L’exposant se réfère à la fonction , tandis que l’indice se réfère à la variable .

Si on nous donne

alors

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

• Récursivité primitive : Kleene utilise le symbole où n indique le nombre de variables ; BBJ utilise . Étant donné :

• étape de base :
• étape d'induction :

Exemple : définition de récursion primitive de

• étape de base : U

Exemple : Kleene donne un exemple de dérivation récursive (notez l'inversion des variables ) . Il commence par des fonctions initiales

5. étape de base :

étape d'induction :

Il arrive à :

• Nombre de Fibonacci
• Fonction McCarthy 91