Quelle est la différence entre les fonctions récursives et les fonctions récursives partielles?


Réponse 1:

La différence est que les fonctions récursives partielles sont, comme son nom l'indique, des fonctions partielles. Une fonction partielle

f:ABf: A \rightharpoonup B

(notez la flèche spéciale!) est une fonction qui est en fait une fonction

f:SBf: S \rightarrow B

où le domaine

SS

est un sous-ensemble de

AA

. Pour toutes les valeurs de

ASA \setminus S

wehavethatfisundefined.If[math]S=A[/math]wesaythatthefunctionistotal. we have that f is undefined. If [math]S = A [/math] we say that the function is total.

C'est la notion de minimisation illimitée qui rend les fonctions partielles. L'opération

μx.P(x)\mu x. P(x)

PP

est un prédicat récursif primitif nous donne le moins

xx

tel que

P(x)=0P(x) = 0

- cependant, il n'est pas nécessaire qu'il y ait des valeurs de

xx

pour laquelle cela vaut.

Dans certains récits de la théorie de la fonction récursive, on définit la minimisation illimitée pour avoir la valeur

00

dans ces cas, et cela garantira alors que toutes les fonctions calculables deviennent totales.