calculabilité

La calculabilité est une branche de la théorie de la logique et de l’informatique qui étudie quelles fonctions ou quels problèmes peuvent être résolus de manière algorithmique. Elle cherche à formaliser la notion de ce qui peut être calculé par une procédure finie et bien définie, indépendamment de la langue ou de la machine utilisée.

Les modèles formels les plus importants sont les machines de Turing, les fonctions récursives et le calcul λ. Ces cadres sont aujourd’hui considérés comme équivalents dans le sens où chacun peut décrire exactement les mêmes ensembles de calculs. La thèse de Church-Turing affirme que toute fonction calculable par intuition peut être calculée par une machine de Turing, par des fonctions récursives ou par un calcul λ.

On distingue calculabilité et décidabilité: une fonction est calculable si elle peut être produite par un algorithme; une langue est décidable si une procédure s’arrête pour toute entrée et répond oui ou non. Certaines langues ou problèmes ne sont pas décidables mais sont semi-décidables (ou récursivement énumérables), ce qui signifie qu’il existe une procédure qui s’arrête et accepte les instances positives mais peut ne pas s’arrêter sur les négatives.

Des résultats emblématiques marquent le domaine: le problème de l’arrêt est indécidable, comme d’autres questions issues du programme de Hilbert et de la logique du XXe siècle. Ces résultats montrent que certaines questions mathématiques ou informatiques ne peuvent pas être résolues par des algorithmes dans le sens intuitif.

La calculabilité forme le socle de l’informatique théorique et influence aujourd’hui la théorie de la complexité et les fondements logiques des systèmes informatiques. Elle permet d’étudier les limites des algorithmes et d’éclairer les distinctions entre ce qui est théoriquement faisable et ce qui ne l’est pas.