À une récente demi-journée d’études sur intelligence artificielle et sciences humaines et sociales, deux intervenants ont soulevé la question de la calculabilité et de l’indécidabilité. Un échange de courriels s’est ensuivi, notamment avec mon collègue Denis Trystram. Je vais résumé ici ma position, qui me semble la même que celle de Denis.

La théorie de la calculabilité établit des bornes à ce qui est calculable par un algorithme, par une version idéalisée d’un ordinateur. Comme résultats notables on a :

  1. Quelle que soit la propriété que l’on veut vérifier sur un programme, plus précisément sur la relation entre les données fournies en entrée et le résultat du calcul, il n’existe aucun algorithme qui permette de décider à coup sûr si un logiciel la vérifie. Autrement dit, il n’existe aucun algorithme capable de décider si un logiciel est correct au vu du code du logiciel. (Théorème de Rice, extension du théorème de l’arrêt de Turing.)

  2. Il n’existe aucune procédure qui dise si un énoncé mathématique est vrai ou faux. (Je simplifie beaucoup, pour plus de précision voir les énoncés des théorèmes d’indécidabilité de Gödel, et aussi le théorème d’indéfinissabilité de Tarski.)

Cette théorie est complétée par celle, un peu plus récente, de la complexité, qui établit notamment qu’il y a des problèmes pour lesquels il existe certes des algorithmes, mais forcément de coût prohibitif.

On a parfois prétendu que ces théorèmes établissent la supériorité de l’esprit humain sur la machine et, comme dans ce colloque, on s’est interrogé sur le lien avec l’intelligence artificielle.

Si, par le passé, on a rangé dans l’intelligence artificielle la réponse à des problèmes dont la définition était très strictement posée en termes mathématiques (démontrer des théorèmes, gagner aux échecs…), l’attention actuelle porte sur des problèmes qui, justement, ne sont pas définis mathématiquement et où l’enjeu consiste en fait à extraire une forme de définition d’une accumulation d’exemples (par exemple, on va apprendre à la machine à reconnaître un mouton en lui montrant une grande quantité de photographies et en lui disant lesquelles contiennent des moutons). Il s’agit par ailleurs souvent de problèmes flous, où il y a des cas tranchés et d’autres où plusieurs réponses seraient admissibles.

Les théorèmes de calculabilité et de complexité ne s’appliquent qu’à des propriétés bien définies mathématiquement. Par exemple, le fait qu’un problème soit de complexité élevée exclut qu’il existe un algorithme efficace dans tous les cas, mais n’exclut pas qu’il existe un algorithme efficace en pratique sur les cas industriellement utiles, car le concept de « cas industriellement utile » est mal défini.

Le rapport entre les questions d’intelligence artificielle proprement dites étudiées actuellement et les résultats classiques de calculabilité ne me semble donc pas évident.