La géométrie des algorithmes – GoA

Le projet GoA part du constat que, contrairement à certaines idées reçues (notamment en logique mathématique), les travaux menés dans les années 1930 par Alonzo Church, Alan Turing, Kurt Gödel et Stephen Kleene ne fournissent pas de définition formelle satisfaisante de la notion d’algorithme. La théorie de la calculabilité vise à caractériser les fonctions calculables de manière algorithmique, mais elle se limite à des algorithmes particuliers, sans préciser ce qu’est un algorithme en général ni comment comparer deux algorithmes (qui calculent la même fonction) entre eux. Elle ne fournit donc pas de conditions d’identité des algorithmes et ne permet pas de leur attribuer un véritable statut ontologique.

Si plusieurs auteurs ont dressé un constat similaire et proposé des cadres formels pour développer une véritable théorie des algorithmes (notamment Andreï Kolmogorov et Vladimir Uspensky dans les années 1950, puis Yannis Moschovakis et Yuri Gurevich entre les années 1990 et 2000), ces approches présentent néanmoins deux limites. D’une part, elles analysent l’algorithme essentiellement à partir de la théorie de la calculabilité et de l’informatique théorique, en négligeant en partie son lien avec la notion de preuve en mathématiques. D’autre part, elles ne distinguent pas suffisamment l’algorithme d’autres notions fondamentales, telles que le programme, le calcul ou le modèle de calcul, parce qu’elles adoptent soit une approche trop syntaxique (l’algorithme comme texte), soit une approche trop sémantique (la structure mathématique interprétant certaines opérations).

Pour dépasser ces limites, le projet GoA étudie la notion d’algorithme dans une perspective dynamique (qui s’affranchit de la dichotomie traditionnelle entre syntaxe et sémantique). Un algorithme est ainsi analysé à partir des actions qu’il permet d’exécuter, lesquelles peuvent être étudiées formellement comme des transformations engendrées par des opérations sur un espace (métrique, topologique, etc.). C’est cette approche géométrique qui donne son titre au projet et c’est une telle approche qui permet aussi de faire un lien avec la notion de preuve, car il s’inspire de certaines techniques venant de la théorie de la démonstration, où les preuves sont étudiées comme des objets de type dynamique (c’est-à-dire, des objets sur lesquels on peut opérer certaines transformations structurelles).

Une telle analyse risque toutefois d’aboutir à une définition trop abstraite, coupée des méthodes algorithmiques employées dans les différentes disciplines. Un objectif essentiel de GoA est donc de vérifier que la définition proposée est compatible avec les usages et les analyses de la notion d’algorithme, non seulement dans les sciences formelles (mathématiques, logique, informatique), mais aussi dans les sciences sociales (droit, sociologie, histoire). L’analyse formelle menée dans GoA est ainsi constamment accompagnée d’une analyse conceptuelle de cette notion.

- Mise en évidence et analyse des différentes acceptions et conceptions de la notion d'algorithme.

Papayannopoulos, P. (2023). « On Algorithms, Effective Procedures, and Their Definitions ». Philosophia Mathematica, vol. 31, n. 3, p. 291-329.

- Distinction conceptuelle entre les notions de modèle de calcul et d’algorithme, ainsi que proposition d’un cadre mathématique permettant de les définir formellement.

Seiller, T. (2026). « Mathematical Informatics: Algorithms ». Dans V. Brattka, H. Fernau et L. Galeotti (dir.), Timeless Machines: Computability Across Eras. Proceedings of the 22nd Conference on Computability in Europe, CiE 2026. Trier, Germany, July 27–31, 2026, p. 86-106. Berlin, Springer.

- Clarification des rapports entre les notions d’algorithme et de preuve.

Naibo, A. (2025) « Preuves et algorithmes ». Dans P. Wagner (dir.), Logique et épistémologie, p. 27–52. Paris, Vrin.

- Analyse des usages des méthodes algorithmiques (et, plus généralement, des méthodes d’IA) dans la recherche de preuves mathématiques.

Dean, W. et Naibo, A. (2025) « Artificial intelligence and inherent mathematical difficulty ». Philosophia Mathematica, vol. 33, n. 3, p. 283–329.

- Analyse de la dimension épistémique de la notion d’algorithme en tant que méthode de résolution de problèmes de type pratique.

Stephanou, H. (2025). Systems, Machines, and Problem-Solving. Berlin, De Gruyter.

(Les travaux présentés ci-dessous sont donnés à titre d’exemple et ne représentent qu’une partie de la production scientifique issue du projet GoA.)

Lorsque le projet GoA a été conçu en 2020, les techniques d’IA fondées sur l’apprentissage statistique existaient déjà, mais elles n’avaient pas encore acquis la visibilité ni l’importance qu’elles ont aujourd’hui. Le projet GoA n’avait donc pas été conçu spécifiquement pour proposer une analyse conceptuelle et formelle de ces techniques. Cependant, l’analyse de la notion d’algorithme menée dans le cadre de GoA peut désormais être mobilisée afin d’éclairer le statut épistémologique des systèmes d’IA fondés sur l’apprentissage statistique.

Un point essentiel qui ressort des réflexions conduites au sein de GoA est qu’un algorithme n’est pas un simple calcul mécanique ou aveugle : il possède une dimension épistémique, dans la mesure où il permet de communiquer, de manière compacte et synthétique, une information sur la façon de résoudre un problème. Un algorithme constitue ainsi une forme de compression de l’information qui permet, à son tour, de mettre en œuvre une action visant à produire une connaissance.

Dans cette perspective, les systèmes fondés sur l’apprentissage automatique ne semblent pas pouvoir être considérés comme de véritables algorithmes. Certes, un système d’IA est conçu pour résoudre un problème de manière mécanique ou automatisée. Toutefois, ce problème concerne généralement des objets dont on ne possède pas de définition formelle a priori. On peut prendre l’exemple d’un système de reconnaissance faciale : un visage n’est pas un objet susceptible d’être défini de manière purement mathématique et formelle. L’approche consiste alors à partir d’une grande quantité de données (des images, par exemple) et à employer des méthodes mathématiques – les modèles d’apprentissage – afin d’identifier des régularités ou des « similarités » entre ces données, puis de produire un programme capable, face à une nouvelle image, de déterminer si celle-ci contient ou non un visage.

Or, si l’on souhaite que quelqu’un d’autre puisse reproduire de manière exacte le comportement de ce programme, il ne suffit pas de lui transmettre le modèle d’apprentissage. Il faut également lui fournir l’ensemble des données initiales, ainsi que le travail d’annotation et de préparation qui les accompagne. Il n’existe donc pas de moyen de communiquer uniquement l’idée générale sous-jacente au comportement du programme. On rencontre ainsi un problème de non compressibilité de l’information.

Dans cette perspective, on pourrait formuler l’hypothèse selon laquelle les systèmes d’IA produisent des programmes qui n’implémentent pas véritablement d’algorithmes. Cela permettrait d’expliquer pourquoi l’IA représente une forme de programmation différente de la programmation traditionnelle et pourquoi il est si difficile d’expliquer le fonctionnement de ces systèmes. Autrement dit, le manque d’explicabilité pourrait être lié à l’absence d’une véritable dimension algorithmique.

Les algorithmes occupent aujourd'hui une place centrale dans le débat public : ils structurent nos interactions sociales et modifient notre façon de travailler, de nous déplacer, ainsi que nos instruments scientifiques et médicaux. Mais qui peut dire exactement ce qu'est un algorithme ? Parce qu'il n'existe aucun consensus parmi les experts, il importe de chercher à donner un fondement épistémologique solide au débat. C'est en effet en leur donnant une représentation mathématique précise que nous pourrons assigner un statut scientifique aux algorithmes. En particulier, l'utilisation des instruments de la géométrie permettra de distinguer la notion d’algorithme de notions voisines et pourtant différentes, comme celle de calcul ou de programme. Une telle analyse permettra ainsi de développer une ontologie propre à l'informatique et de faire de cette dernière une théorie mathématisée, au même titre que la physique.