Un article de Wikipedia.y-project.com.
La théorie de la calculabilité (ou parfois théorie de la récursion) est une branche de la logique mathématique ou de l'informatique théorique, initiée par Alan Turing, qui s'intéresse à la délimitation des catégories des fonctions calculables et non calculables, et aux concepts dérivés. L'exemple le plus courant est le problème de l'arrêt : il n'existe pas de programme qui prenne un programme en argument et dont on soit sûr qu'il renvoie « oui » si le programme en argument finit et « non » s'il ne finit pas.
En lambda-calcul, il y a le terme (?x.xx)(?x.xx) qui n'est pas normalisable.
Plusieurs modèles de calcul sont utilisés en calculabilité :
[] Concepts
Voir aussi Théorème de récursion de Kleene, lambda-calcul
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Théorie de la calculabilité
