Fonction semi-calculable - Définition
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
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 :
-
- μ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)
