Accueil > Hypercomplex > Théorie de la calculabilité

Théorie de la calculabilité

mercredi 30 août 2006, par Petit poney

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



Voir en ligne : Wikipedia.org

Répondre à cet article