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

• 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

 

Réagissez

Commentez l'encyclopédie:
Attention! tous les commentaites inaproprié seront supprimés

Titre:
Video YouTube ou google:	(doit être en rapport avec le sujet)
Votre mail:	(ne sera pas affiché sur le site)
Un pseudo:
Votre site:
Commentaire	(le html n'est pas autorisé, nombre de caractère maximum = 400)
	(Comment eBabylone 1.0 beta)

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é