C'est par son titre que cette monographie sur les théories de l'Indécidabilité relève des lectures en sciences de la complexité : en définissant la complexité mesurable par la difficulté de la résolution d'un problème de décision (au sens de Hilbert : la difficulté d'une démonstration formelle en mathématique), les mathématiciens de profession s'attribuent de nouveaux domaines de recherche en les rebaptisant : ils avaient établi, depuis 1928, "le domaine de l'Indécidabilité" ; en l'appelant "domaine de la Complexité", ils suggèrent peut-être aux recherches en sciences de la complexité quelques voies d'invesdgation encore insuffisamment explorées ? Suggestion implicite ou involontaire dans le cas de cet ouvrage de P. Dehornoy, qui ne retient le concept de complexité qu'incidemment, parce que les théorèmes d'incomplétude (ou d'indécidabilité) de l'arithmétique et de la logique mathématique sont parfois présentés sous le titre des "théories de la complexité" (...de la computation), théories qui ne s'attachent pas à définir ou à caractériser la complexité d'un systéme, mais à mesurer la difficulté relative de résolution algorithmique (éventuelle) d'un problème de logique formelle.

Ce glissement subreptice d'intitulé s'avère pourtant fort utile - sans doute à l'insu des mathématiciens - pour les chercheurs en quête de "logiques de l'enquête" (J. Dewey) : en exposant avec brio et élégance, l'universalité et la robustesse de la théorie de la Machine de Turing, puis en re-démontrant, par ce recours, l'essentiel des théorèmes d'incomplétude de Gödel (étendu de l'arithmétique aux logiques de premier et de deuxième ordre), P. Dehornoy nous accoutume au bon usage de toute une variété d'outils mathématico-informatiques : "Simulation l'algorithmes, accélération par changement d'alphabet, contrôle par fonctions récursives, arguments d'auto-référence, processus non déterministes, réduction et codage..." (p. 4). La puissance modélisatrice de la Machine de Turing nous apparait ainsi, fort pédagogiquement présentée. (Son livre est un cours de troisième cycle, qui ne requiert pas de préalables en théorie de la computation). C'est ainsi, par exemple, que les limites révélées par le théorème d'indécidabilité pour les logiques de premier ordre méritent d'être réfléchies par les praticiens du langage PROLOG, "dont les instructions sont des formules du premier ordre". H.A. Simon et D. Kaplan avaient déjà souligné ce point (en examinant les langages LISP et PROLOG) dans leur célèbre article de "Foundations of Cognitive Science" de 1990 (cf. la Lettre MCX n°12, mai 1991). Mais exposé par un mathématicien français, l'argument sera sans doute plus convaincant.

On regrettera bien sûr que cette belle lecture de la thèse de Turing (qui date de 1936) ne privilégie que son aspect "négatif" : démontrer une impossibilité. Faut-il rappeler que dès 1952 (année de la mort de Turing) A. Newell et H.A. Simon montraient l'importance "constructive" de cette même thèse, sur laquelle ils allaient fonder l'Intelligence Artiricielle à partir de 1956 : la Machine de Turing permet aussi de "représenter" (ou de modéliser) tout "raisonnement" (quantitatif et qualitatif), qu'il converge ou non, et donc de le reproduire ou de le simuler, dès lors qu'on peut le décrire par "un traitement de listes de symboles", autrement dit par des symboles computables pouvant être computants et computés : le concept d' "heuristique programmable" était né et avec lui les premiers "programmes" d'I.A. (LT, GPS...). Argument qui s'avérera vite essentiel pourl'élaboration des stratégies de recherche ("search") qui rendent aujourd'hui possibles et effectifs les développements des sciences de la complexité : "Modéliser n'est ni plus ni moins logique que raisonner (au sens de "démontrer")" concluait déjà H.A. Simon, qui ajoutait : "La modélisation (des raisonnements qualitatifs) est notre principal outil d'étude des grands systèrnes complexes" (Conférence à l'IIASA, 1989-90)... En observant, une fois encore, l'exceptionnelle expérience modélisatrice accumulée par les mathématiciens depuis 25 siècles, on voudrait inviter les mathématiciens d'aujourd'hui à mettre cette expérience autant au service de la modélisation de la complexité qu'à celui de la démonstration de l'incomplétude de la logique formelle. A eux et à nous de susciter les échanges et les langages... N'est-ce pas la vocation du Programme MCX ?

J.L. Le Moigne.