Calculabilité Logique mathématique

La théorie de la calculabilité (ou parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique, initiée par Alan Turing, qui cherche d'une part à identifier la classe de fonctions qui peuvent en principe être calculées à l'aide d'un algorithme et, d'autre part, à étudier les questions reliées aux limites fondamentales de la calculabilité.

Il peut-être démontré qu'il existe des fonctions f qui sont incalculables, c'est à dire qu'il n'existe aucun algorithme qui, étant donné x, retourne toujours la valeur f(x) en un temps fini. L'exemple le plus courant est celui du problème de l'arrêt : il n'existe pas de programme qui prenne un programme en argument et qui, en temps fini, renvoie « oui » si l'exécution du programme reçu en argument finit par s'arrêter et « non » s'il ne finit pas.

Plusieurs modèles de calcul sont utilisés en calculabilité:

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

Malgré les apparentes différences de ces modèles, la classe de fonctions calculables par chacun de ceux-ci est unique et cette constatation mène à la thèse Church-Turing.

Concepts

• Ensemble récursif
• Récursivement énumérable
• Hiérarchie arithmétique
• Thèse de Church-Turing

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

نظرية الحسوبية | Teorie vyčíslitelnosti | Berechenbarkeitstheorie | Computability theory (computer science) | Teoría de la computabilidad | نظریه محاسبه‌پذیری | Teoria della calcolabilità | 計算可能性理論 | 계산 가능성 이론 | Berekenbaarheid | Teoria obliczalności | Теория вычислимости | Computability theory | ทฤษฎีการคำนวณได้