Calculabilité

Un article de Freepedia.

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é :

• machines de Turing
• lambda-calcul
• automates cellulaires
• fonctions récursives

Concepts

• Ensemble récursif
• Récursivement énumérable
• Hiérarchie arithmétique

Voir aussi Théorème de récursion de Kleene, lambda-calcul