Fonction semi-calculable

Les fonctions récursives peuvent être obtenues en ajoutant aux opérateurs permis dans la définition des fonctions récursives primitives le schéma µ, à savoir :

${\displaystyle \mu _{f}(x_{1},...,x_{n})={\textrm {inf}}_{y}\{f(y,x_{1},...,x_{n})=0\}}$

Autrement dit, ${\displaystyle \mu _{f}(x_{1},...,x_{n})}$ calcule le plus petit y annulant ${\displaystyle f(y,x_{1},...,x_{n})}$. Si un tel y n'existe pas, le calcul de la fonction ${\displaystyle \mu }$ ne se termine pas.

En termes plus intuitifs, cela revient à rajouter les boucles tant-que (while) dans un langage qui n'aurait que des boucles pour-tout bornées (for), le calcul de y pouvant être opéré comme suit :

y = 0

while ${\displaystyle f(y,x_{1},...,x_{n})}$ <> 0 do y := y+1 od

return(y)

Un algorithme, ou un programme, calculant la fonction :

${\displaystyle {\begin{matrix}f:&D\subset \mathbb {N} &\rightarrow &\mathbb {N} \\&x&\mapsto &f(x)\end{matrix}}}$

est appelé une fonction partielle récursive. Partielle car son ensemble de définition, son domaine, est un sous-ensemble ${\displaystyle D\subset \mathbb {N} }$. Si son domaine est ${\displaystyle \mathbb {N} }$ tout entier, alors il s'agit d'une fonction récursive totale. La fonction est dite récursive car elle est calculable par un algorithme, c'est-à-dire qu'un ensemble fini d'instructions est capable de fournir, après un nombre fini d'étapes, la valeur ${\displaystyle f(x)}$ quel que soit ${\displaystyle x\in D}$. L'algorithme doit spécifier l'étape suivante à partir de l'étape précédente de manière non ambigüe, et pour toute valeur de ${\displaystyle x}$ du domaine[1].

• Fonction récursive