La calculabilité

La calculabilité est la théorie mathématique des fonctions calculables en droit par un algorithme. Fondée durant les années 1930 pour résoudre des problèmes de logique et fondements des mathématiques, elle s’est révélée a posteriori féconde pour théoriser les limites ultimes des ordinateurs, en ce que ceux-ci exécutent des algorithmes rédigés dans un langage formel de programmation. La calculabilité s’abstrait à dessein des limites concrètes pesant sur les ressources nécessaires au calcul, comme le temps et l’espace mémoire. Mais on peut enrichir les objets créés par cette théorie pour prendre en compte ces limitations, et formuler une théorie de la complexité intrinsèque des problèmes algorithmiques. Une telle théorie est nommée « théorie de la complexité computationnelle ». Elle vient compléter la calculabilité pour former la théorie du calcul. Ce chapitre du Précis vise à une présentation succinte de cette théorie du calcul, et de certains de ses enjeux philosophiques. Il se veut accessible aux philosophes versés dans la logique, comme aux mathématiciens et informaticiens intéressés par les fondements du calcul. Dans un premier temps, nous présentons les concepts de base de la calculabilité. Dans un deuxième temps, nous exposons l’expansion de cette théorie au calcul sur les réels. Enfin, nous introduisons les fondements de la théorie de la complexité computationnelle.