Fonction semi-calculable
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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~ (Hiérarchie arithmétique).

Exemple

Les fonctions récursives peuvent être obtenues en ajoutant aux opérateurs permis dans la définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) 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)
Page générée en 0.021 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique