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 plus petite classe de fonctions incluant les fonctions initiales et stable par composition et récursivité primitive (c'est-à-dire sans minimisation) est celle des fonctions récursives primitives . Toutes les fonctions récursives primitives sont totales, ce qui 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 elles-mêmes un sous-ensemble des fonctions récursives partielles. Par exemple, on peut démontrer que la fonction d'Ackermann est totalement récursive et non primitive.

Fonctions primitives ou « basiques » :

1. Fonctions constantes : Pour tout entier naturel

   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 projectionfonction identité ) : Pour tous les nombres naturels

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 compositionopérateur de substitution ) : Étant donné une fonction m -airem fonctions k -aires

   Cela signifie que

2. Opérateur de récursion primitive : Étant donné la fonction k -airek + 2-aire

   Cela signifie que

3. Opérateur de minimisation : Étant donné une fonction ( k +1)-airek -aire

   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 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’existe pas un tel argument, ou si l’on rencontre un argument pour lequel n'est pas défini pour l'argument

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 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

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.

Exemples

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$x(z+1{)}^2>x$x En utilisant l'opérateur de minimisation, on obtient une définition récursive générale :Not , Gt , et Mul sont respectivement la négation logique , le supérieur à et la multiplication, . En fait,$x)(\mathrm{Pas}\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) est0 si et seulement si,$xS\left(z\right)\ast S\left(z\right)>x$x tient. Par conséquent.z tel que$xS\left(z\right)\ast S\left(z\right)>x$x tient. Le connecteur de négation Not est nécessaire puisque Gt encode la vérité par1 , 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.

fonction d'Ackermann