Sommes-nous des machines de Turing ? Excusez la brutalité du propos… La question, certains neuro-cogniticiens se la posent, quitte à faire sourire. Le pauvre Alan n’aurait sûrement jamais osé aller jusque là. Alan Turing ? Oui, celui à qui on doit l’invention de l’informatique, par le biais de la réponse au « problème de la décision » posé par Hilbert au début du XXème siècle (est-il possible de répondre par oui ou par non à toute question mathématique, pourvu qu’elle soit posée et formulée dans un bon langage ?), la résolution des codes secrets allemands grâce à la machine Enigma, les prémices de l’intelligence artificielle, mais aussi celui qui souffrit des tracas causés par la justice anglaise, demeurée affreusement victorienne, une condamnation pour homosexualité, la déprime, et la mort par ingurgitation de la pomme empoisonnée, qui fait de lui un Socrate des temps modernes… et celui pour qui seulement l’an dernier fut prononcée une réhabilitation à titre posthume par le premier ministre Gordon Brown soi-même.(voir ici mon billet d’octobre 2009). Alan Turing, donc, en répondant au fameux problème ci-dessus (par la négative, disons-le tout de suite) mit à jour un concept précis d’algorithme. Est algorithme tout ce qui peut se ramener à un enchaînement d’instructions très simples, du genre : lire un symbole sur une case d’un ruban (supposé de longueur infinie), en fonction du symbole lu, passer dans un état ou un autre, dans cet état, se déplacer sur le ruban pour éventuellement y écrire quelque chose, puis recommencer. Cela n’a l’air de rien, mais avec ça on peut (presque) tout faire, c’est-à-dire toutes les opérations arithmétiques, et plus généralement tout ce qu’est capable de faire un ordinateur d’aujourd’hui. Et pour cause, puisque lesdits ordinateurs dérivent du modèle de Turing. Evidemment, il y a des choses que l’on ne peut pas faire et qu’on ne pourra jamais faire (c’est démontré), comme répondre à l’avance au problème de savoir si une machine de Turing quelconque, lancée sur une donnée quelconque, va s’arrêter. Il y a aussi des problèmes qu’on peut théoriquement résoudre, mais en un temps qui croît tellement vite (exponentiellement) en fonction de la taille des données que, pratiquement, on n’y arrivera pas non plus, et tombent là-dedans presque toutes les tâches que nous, humains, savons si bien faire avec un peu d’apprentissage, comme lire par exemple (et comprendre ce qu’on lit), mais aussi des tâches en apparence futiles comme optimiser le parcours d’un voyageur de commerce qui veut visiter ses points de vente pas plus d’une fois en empruntant le circuit le plus court…

(machine Enigma)

N’y a-t-il qu’un seul modèle permettant de calculer ? Non, d’autres ont tenté de résoudre le problème résolu par Turing à partir de bases voisines ou totalement différentes, par exemple la théorie dite des fonctions récursives (ou lambda-calcul), élaborée par Alonzo Church, ou bien le modèle des machines RAM (random access memory) du à von Neumann. La chose intéressante est qu’aucun de ces modèles n’est plus puissant qu’un autre : tous se valent. Tout ce qui s’exprime dans l’un s’exprime dans l’autre. Il y aurait donc une sorte de limite insurpassable de la calculabilité. Evidemment ceci n’est pas démontré, ne peut pas l’être car dès qu’on voudrait le faire, il faudrait nécessairement proposer une définition du calcul selon un certain modèle et cela ne serait alors qu’un modèle de plus et on ne pourrait pas dire que c’est la « vraie » notion de calcul par rapport à laquelle on juge les autres. Néanmoins, on a de sérieuses raisons de croire qu’il en est ainsi et cette idée est formulée sous le nom de « thèse de Church-Turing ».

Dès que les ordinateurs sont apparus, le fantasme est né d’y voir une représentation de la manière dont nos cerveaux fonctionnent. On aurait dû faire très attention pourtant car devaient vite sauter aux yeux de tous les différences flagrantes entre eux et nous, comme leur incapacité pratique à faire certaines tâches dont nous nous acquittons facilement, contrastant avec l’aisance ahurissante dont ils font preuve pour effectuer des calculs qui nécessiteraient de notre part des années de travail…. Mais non, une « solution » était là, il fallait donc trouver la question correspondante !

Dans les années quatre-vingt-dix, de gros espoirs furent fondés sur les machines parallèles. Il est assez évident que, si nos cerveaux fonctionnent si différemment des machines de Turing, c’est parce que ces dernières sont séquentielles (une tâche à la fois) alors qu’il semble que nous effectuions des multitudes d’« opérations mentales » en même temps. On se mit donc à imaginer des machines dites « connexionnistes » (ou à parallélisme massif), mais il apparut que le seuil de la complexité n’était pas franchi pour autant, c’était la durée de l’apprentissage qui s’allongeait exponentiellement au lieu du temps d’exécution. Et puis les informaticiens n’arrivèrent jamais à mettre au point une algorithmique parallèle : nous savons formuler consciemment des algorithmes séquentiels mais pas des parallèles. Et aujourd’hui encore les grands centres de calcul fonctionnent avec des machines à architecture de von Neumann (même si on conjugue les efforts de centaines, voire de milliers d’entre elles au sein de réseaux énormes). Et l’intelligence artificielle n’a pas beaucoup progressé pour autant… renvoyant les rêves d’esprit super-intelligent chers à quelques sectes californiennes au rayon des délires de science-fiction.

Cela n’empêche pas que l’assimilation du cerveau humain aux machines de Turing ressorte de temps en temps. La dernière fois, c’est par la plume d’un neuro-scientiste américain, un certain Randy Gallistel, dont l’ouvrage, Memory and the Computational Brain, semble avoir ces temps-ci un certain succès. Gallistel veut montrer que pour fonctionner correctement, notre cerveau a besoin d’un ruban, comme la machine de Turing, c’est-à-dire en termes un peu moins triviaux, d’une mémoire sur laquelle il soit possible de lire et d’écrire (« a read-write memory »). Pas la peine d’attendre 2010 pour savoir en effet que les problèmes les plus simples à résoudre, vous n’arriverez pas à le faire avec simplement une machine qui se contente de changer d’état interne sans garder la mémoire des étapes antérieures. Ce que fait une machine sans ce genre de mémoire est extrêmement limité, elle ne sait même pas compter… mais si une forme de mémoire est nécessaire (qui en douterait ?), en revanche, elle est sans doute loin d’être suffisante. Or Gallistel pense « révolutionner les neuro-sciences » rien qu’avec cette idée et il s’avance triomphalement en clamant que nos cerveaux fonctionnent « comme » des machines de Turing (et pourquoi pas alors si c’était le cas d’après un des autres modèles inventés pour rendre compte de la calculabilité ?).
Il faut faire, à mon avis, attention à une certaine science moderne, qui élabore des modèles très complexes en partant de bases douteuses. Ici la base est (répétée à profusion) que nos cerveaux calculent. N’importe qui devrait demander alors aux savants cogniticiens qui avancent cet axiome : mais dans quel sens entendez-vous « calculer » ? On se rendrait alors évidemment compte qu’on ne peut pas donner un sens précis à cette notion sans… invoquer un des modèles dont je parlais plus haut. Autrement dit, la réponse à la question « comment nos cerveaux calculent ? » est déjà dans la question, ce qui est fort peu scientifique. On n’ignore pas impunément les limitations constatées en logique et en mathématiques depuis longtemps.