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 (Hiérarchie arithmétique).
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 :
μf(x1,...,xn) = infy{f(y,x1,...,xn) = 0}
Autrement dit, μf(x1,...,xn) calcule le plus petit y annulant f(y,x1,...,xn). Si un tel y n'existe pas, le calcul de la fonction μ 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,x1,...,xn) <> 0 do y := y+1 od
return(y)