calculabilité
Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».
Du latin calculus, « petite pierre », et, par extension, « calcul » (opération de comptage primitivement effectuée à l'aide de cailloux).
Logique
Propriété d'une fonction pour laquelle il existe un algorithme de calcul, c'est-à-dire dont la valeur pour un argument donné peut être uniformément obtenue par une méthode effective ou mécanique. Ainsi, l'addition des entiers naturels est une fonction (effectivement) calculable.
Née dans les années 1930 de tentatives pour montrer que certaines fonctions n'étaient pas effectivement calculables, la théorie de la calculabilité est aujourd'hui une branche importante de la logique mathématique ; elle joue, notamment, un rôle central dans l'analyse et la mise au point des machines informatiques.
Jacques Dubucs
Notes bibliographiques
- Boolos, G.S., et Jeffrey, R.C., Computability and Logic, Cambridge UP, 1996.
→ Church (thèse de), décidabilité, effectivité, machine (logique, de Turing)