Fonction semi-calculable

En informatique théorique, les fonctions semi-calculables ou fonctions partielles récursives sont les fonctions calculables par les machines de Turing ou tout autre système de programmation Turing-complet.

En logique mathématique, les fonctions semi-calculables correspondent aux relations fonctionnelles $\Sigma _{1}~$ (voir Hiérarchie arithmétique).

Exemple

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 :

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

Autrement dit, $\mu _{f}(x_{1},...,x_{n})$ calcule le plus petit y annulant $f(y,x_{1},...,x_{n})$. Si un tel y n'existe pas, le calcul de la fonction $\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 $f(y,x_{1},...,x_{n})$ <> 0 do y := y+1 od

return(y)