Le contexte de l’article de 1936 « Théorie des nombres calculables, suivie d’une application au problème de la décision »

Paris, le 22/08/2011

Dans cet épisode, on va essayer d’avancer vers l’article de 1936, « Théorie des nombres calculables, suivie d’une application au problème de la décision »[1].

(Je me rends compte par ailleurs que plus j’essaie « d’avancer » vers cet article, plus j’ai l’impression d’être Achille tentant de rattraper la tortue…)

Pour ce faire, je voudrais revenir sur ce que j’ai écrit précédemment. Car en relisant ma précédente présentation du programme de Hilbert, je me suis rendu compte qu’il était aisé de finir par la concevoir de façon simplifiée.

J’ai écrit que ce que l’on nomme consistance de l’axiomatique formelle c’est le fait qu’aucune formule contradictoire ne peut y être engendrée à partir des axiomes.

Et il est vrai que, à certains moments, Hilbert a distingué deux activités, celle du mathématicien, qui raisonne principalement sur des signes, en excluant la signification, et celle du métamathématicien, qui, cette fois, réintroduit le contenu, autrement dit, le sens. « Dans cette métamathématique, à l’opposé de ce qui se fait dans les procédés de raisonnement purement formels de la mathématique proprement dite, on applique un raisonnement doué de contenu, et cela pour établir la consistance des axiomes. »[2]

Mais, comme l’écrit Girard, « Une simplification outrancière du point de vue de Hilbert nous donne : les mathématiques sont une activité purement formelle, sans plus de signification que le jeu d’échecs. Pour démontrer, nous utilisons des axiomes et de la logique, mais notre intuition de ces entités est douteuse. Il faut donc objectiver ce qui se passe, en se contentant d’analyser le jeu formel de signes sous-jacent, de façon à démontrer sa consistance c’est-à-dire le fait qu’il ne mène pas à contradiction. Cette formulation sombre immédiatement dans le ridicule : il serait en effet absurde de dire d’une part que les énoncés mathématiques n’ont aucun sens, pour d’autre part mettre l’accent sur la propriété métamathématique de consistance, qui est aussi un énoncé mathématique. »[3] Ainsi, Hilbert ne faisait que séparer de manière rigoureuse deux façons de raisonner, selon que l’on raisonnait dans le système, ou sur le système des mathématiques. Mais il est impossible d’évacuer au final l’intuition et le sens des mathématiques, y compris dans la conception hilbertienne de ces derniers.

Consistance et complétude

Une autre formulation de la consistance pourrait être de dire qu’un système formel est consistant si, de deux formules contradictoires, A et ­­­­­­­­­non-A, l’une au moins n’est pas démontrable, et qu’il n’est donc pas possible de prouver A et non-A simultanément dans ce système.

Une autre formulation de la complétude serait alors de dire qu’un système formel est complet si, de deux formules contradictoires, A et non-A, l’une au moins est démontrable, et qu’il est alors nécessaire de pouvoir prouver ou A, ou non-A, dans ce système.

Rappelons-nous qu’en 1900 Hilbert avait soumis aux mathématiciens 23 problèmes. Gottlob Frege (avec qui Hilbert avait correspondu et était justement en opposition sur la nature de ce qu’était un axiome) s’était attaqué aux fondements des mathématiques dans son livre homonyme de 1884. Il abordait le problème d’un point de vue logique, et pour lui, « l’arithmétique découlait des relations logiques entre les entités de ce monde, et dont la consistance était assurée par une relation avec la réalité. »[4]

Le second problème de Hilbert portait sur cette même consistance des « axiomes de Peano » dont il faisait dépendre toute la rigueur des mathématiques. On pourrait dire que la préhistoire de la métamathématique de Hilbert était en effet une reprise de l’axiomatique telle qu’elle avait été proposée par Euclide, puis une autre reprise portant cette fois sur la tentative de fonder l’objet nombre de manière mathématique.

Dans une autre orientation, Bertrand Russel avait introduit l’idée d’ensemble dans l’orientation théorique ouverte par Frege, notamment avec sa tentative de définir le nombre UN, comme « l’ensemble de tous les ensembles à un élément »[5]. Mais l’on connait les paradoxes qui surgissent lorsqu’on manipule ces ensembles de tous les ensembles… Russel et Alfred North Whithead (1861 – 1947) travaillèrent longuement sur leur Principia Mathematica, précisément pour élaborer certaines solutions inhérentes à l’utilisation des ensembles dans ce cadre. Il en ressortit ce que l’on appelle « la théorie des types », qui sera critiquée par Wittgenstein par ailleurs dans ses travaux de logique. Pour tente d’éviter de faire surgir ces paradoxes, Russel et Whitehead définissaient des types d’ensembles. Turing s’intéressa par ailleurs à « L’introduction à la philosophie mathématique » de Russel.

Mais c’est en 1928, alors que le programme de Hilbert était à son apogée, lors du congrès de Bologne, que Hilbert signala « quatre problèmes encore à résoudre et demandait en particulier de démontrer : la complétude sémantique du calcul des prédicats, la consistance et la complétude syntactiques de l’arithmétique formelle. »[6]

En 1930, le jeune logicien viennois Gödel apportera une réponse positive à la complétude sémantique du calcul des prédicats. Mais il allait par contre l’année suivante mettre un coup d’arrêt à l’optimisme du programme de Hilbert, en montrant les limites de la formalisation dans un mémoire devenu célèbre, et qui allait tracer la voie à des recherches sur l’indécidabilité. Nous reviendrons sur ce point un peu plus loin.

Sautons quelques années pour nous retrouver fin 1933. Sur la scène mondiale, la montée du nazisme provoque l’exil de nombreux scientifiques vers l’Angleterre et les Etats-Unis. C’est alors le déclin de la fameuse université de Göttingen, le fief de Hilbert. Einstein émigre vers Princeton. Von Neumann part également pour les Etats-Unis. Turing, sans être directement politisé, a des affinités avec le mouvement anti-fasciste. Il passe ses examens, et ses résultats lui valent une bourse de recherche au King’s College de Cambridge. Ainsi, en novembre 1934, il termine son mémoire et en mars 1935, il est reçu premier de son année. A 22 ans, il obtient alors une bourse de 300 livres par an, pendant 3 ans. Et au même moment, il publie son premier article dans le London Mathematical Society. « Il s’agissait d’une petite découverte touchant à la théorie des groupes, qu’il annonça le 4 avril à Philip Hall […] », qui est un spécialiste de la théorie des groupes. « Les recherches d’Alan complétaient un article de von Neumann […] », qui était de passage à Cambridge en avril 1935, et que Turing rencontra peut-être.

Démontrabilité

Comme je l’ai précisé en fin d’épisode 6, Kurt Gödel (1908 – 1978) s’est attaqué au programme de Hilbert, pour l’ébranler sérieusement avec son fameux article de 1931, « Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés I» (le II n’a jamais été crit). C’est sur le plan de la complétude de l’axiomatique formelle, mais également sur celui de la consistance, que Gödel travailla. Il démontra ainsi « qu’une axiomatique formelle susceptible de servir de réplique à l’arithmétique des entiers est structurellement incomplète : on peut montrer qu’il y a un « reste » arithmétique qui échappe à l’axiomatique formelle quels que soient les aménagements axiomatiques ultérieurs susceptibles de se produire. Il fallait en conclure que la démontrabilité d’un énoncé n’était pas strictement équivalente à sa vérité puisqu’un théorème (un énoncé vrai) pouvait être vrai sans être déductible des axiomes : il devenait nécessaire de dissocier la déductibilité de nature syntaxique et la vérité de nature sémantique au sein de l’axiomatique formelle.»[7]

Et, même si c’est sur un autre plan, celui de la décidabilité, que Turing va œuvrer, c’est d’une certaine manière, dans l’ombre du génial logicien Gödel, qu’il va publier son article sur la théorie des nombres calculables. Nous allons voir pourquoi.

Pour tenter d’approcher l’article de Turing, il me semble qu’il faut retracer à grands traits la notion de calcul, avant de l’articuler à celle de décidabilité (car pour résoudre le problème de la décision, tel énoncé est-il décidable, il faut finalement savoir ce qu’est un calcul), pour parler enfin de la démarche, similaire à celle de Gödel, qu’emprunta Turing (l’arithmétisation de la métamathématique). Au final, retenons le fait que « le problème de la décision est ainsi ramené à celui de savoir si une fonction est calculable. »[8]

La notion de calcul : de la fonction à l’algorithme

C’est seulement dans les années 1920 que l’on commença à s’interroger de manière approfondie sur ce qu’est cette notion de calcul, « outil de la démarche mathématique, elle n’était pas devenue objet mathématique. »[9]

Au 18^ème siècle, eu lieu l’émergence de la théorie des fonctions. Et dès lors, « la notion de calcul fut associée à la notion de fonction […] à une valeur numérique de x correspondait, par une transformation effectuée par la fonction f, une valeur  f(x).»[10].

Puis au cours du 19ème siècle, sous l’avancée des recherches en théorie des ensembles, c’est la notion de fonction qui va elle-même évoluer, « jusqu’à signifier une correspondance quelconque entre éléments d’un ensemble de départ vers un ensemble d’arrivée sans que fut envisagée une procédure effective de calcul. »[11]

Une fois cette définition de la fonction acquise, le problème va être de savoir si effectivement il existe une procédure de calcul pour telle ou telle fonction particulière. On va pouvoir ainsi définir une classe générale de fonctions, et une sous-classe qui sera celle des fonctions dites calculables, lorsque l’on peut trouver effectivement une procédure de calcul. Mais à présent, comment cerner concrètement cette sous-classe des fonctions calculables ? On retombe ainsi sur le problème de ce qu’est véritablement une « procédure de calcul ».

Et c’est à ce point que l’on peut faire entrer la notion d’algorithme. « Le terme ‘algorithme’ dérive du nom d’un mathématicien de langue arabe originaire d’Asie Centrale – Al Khowarismi – qui vivait dans cette capitale scientifique qu’était Bagdad au IXème siècle et à qui l’on doit notamment d’avoir transmis des mathématiciens indiens la numération de position et d’avoir écrit l’un des premiers traités d’algèbre […] »[12]. Un algorithme est ainsi une sorte de recette, de méthode, de procédure systématique qui nous donne « la liste d’instructions que l’on doit suivre pour réussir à atteindre un résultat après un nombre fini d’étapes. »[13]

Si vous souhaitez écouter une bonne émission sur ce sujet : http://radiofrance.saooti.com/fr/broadcast/36_Genese_dun_algorithme

Lorsqu’on manipule les propriétés de certains ensembles, du type entier naturel, et que l’on s’en tient à des cas précis, ou lorsqu’on veut rechercher les occurrences d’un nom donné dans un fichier, et répondre, soit oui, le nom s’y trouve, soit non, il ne s’y trouve pas, il n’y a pas vraiment de problème. On touche là à la question de la décision. Si l’on s’en tient à des ensembles finis, pas de problème particulier. On peut par exemple dresser des listes.

Mais si l’on commence à travailler sur des ensembles infinis, on va commencer à se heurter à certains soucis. Par exemple, si l’on veut s’assurer que certains énoncés peuvent être applicables sur tous les nombres entiers naturels, ou bien tester sur tous les noms possibles, les difficultés commencent.

Lacan et la logique de la cure selon Miller

Pour faire un parallèle avec la psychanalyse orientée par Lacan. Certains lacaniens se sont posés la question si l’ensemble des signifiants essentiels pour un sujet était un ensemble fini ou infini par exemple. En effet, si l’on voulait définir « une logique de la cure » qui tenterait de formaliser non pas la structure du sujet, mais de formaliser les transformations qui s’opèrent au sein de cette structure du sujet au cours de la cure, la question pouvait se poser. Selon Jacques-Alain Miller, le Séminaire IV de Lacan, La relation d’objet, proposerait en effet une tentative « d’utiliser le schéma L au moins pour formaliser le changement de position subjective d’un point de vue clinique. »[14] En tentant ainsi de penser les transformations dans la cure, comme des permutations de termes au sein d’un jeu de place au sein de la structure, on se trouve devant le fait qu’il faille poser au préalable un nombre fini de signifiants essentiels. La conclusion de cette logique de la cure pensée ainsi, sera alors obtenue au terme d’un certain nombre de permutations. Cette logique par permutation s’oppose à une logique linéaire, c’est-à-dire à une déduction qui démarre des prémisses pour arriver à une conclusion. Enfin, si l’on suit Miller lisant Lacan dans « L’instance de la lettre dans l’inconscient ou la raison depuis Freud » où ce dernier résume sa recherche sur le petit Hans dans son séminaire IV de la même année 1957, ce serait également une démonstration par l’absurde, et non une démonstration positive. « Lacan dit là que ‘le petit Hans […] développe, […] sous une forme mythique, toutes les permutations possibles d’un nombre limité de signifiants’. Ce que l’on obtient est la solution de l’impossible, à savoir que la démonstration qu’apporte la cure conçue à partir de la logique de la cure relève de la démonstration par l’absurde ; elle se conclut par un ‘il n’y a pas’, par un ‘ce n’est pas le cas posé dans l’hypothèse’. Telle est l’orientation fondamentale de Lacan depuis son étude de la cure du petit Hans. La transformation de l’impuissance en impossibilité, comme il le formulera dans les années soixante-dix, est déjà présente dans ce Séminaire IV. On y trouve aussi inscrite la formulation de la fin de l’analyse comme perception, subjectivation du ‘il n’y a pas de rapport sexuel’.»[15] Nous essaierons peut-être de creuser cela dans notre lecture de ce séminaire, La relation d’objet.

Mais revenons à la notion d’algorithme et à son rapport avec le calcul et le problème de la décision. Car c’est là que la notion d’algorithme est censée permettre de répondre à tous les cas possibles, et non plus au cas par cas. Soit dans le cas des entiers naturels, être capable de répondre par exemple si n est vraiment un nombre premier. D’où le fait qu’un algorithme est aussi une procédure de décision.

Dans ce cadre, et pour en revenir au problème de la décidabilité de l’axiomatique formelle, c’est la question « de savoir s’il existe une méthode algorithmique qui puisse décider si une formule quelconque est ou non déductible des axiomes de l’axiomatique formelle. »[16]

La méthode : arithmétisation de la métamathématique

Afin de s’attaquer à la complétude, ainsi qu’à la consistance de l’axiomatique formelle, Gödel avait opéré une stratégie que l’on nomme arithmétisation de l’axiomatique formelle. Et c’est la même stratégie que Turing utilisera.

En quoi cela consiste-t-il ? Nous avions montré que l’axiomatique formelle se distinguait des axiomatiques à contenu justement par le fait que la première était censée se substituer à toutes les secondes. Hilbert voulait précisément remplacer le détour par l’expérience comme preuve, par un détour qui reste interne aux mathématiques, ce qui revenait, pour tester la non-contradiction d’une axiomatique, à la remplacer par une autre axiomatique plus fondamentale, et ainsi de suite. Pour ce faire, nous avions montré que Hilbert avait distingué deux sortes d’axiomatiques. « L’axiomatique à contenu – celle qui s’était toujours pratiquée, chez Euclide pour la géométrie ou chez Peano pour l’arithmétique – et l’axiomatique formelle. » L’axiomatique formelle est alors censée offrir un espace où l’on peut répliquer les axiomatiques à contenu dont il était difficile de prouver la non-contradiction.

Mais alors pourquoi revenir à l’arithmétique ? Car « […] l’instrument de cette fidélité [entre l’axiomatique à contenu et l’axiomatique formelle] peut précisément être le nombre. […] une fois constituée l’axiomatique formelle, celle-ci peut, précisément parce qu’elle n’a plus de signification, être recodée de façon rigoureuse sous forme de nombres. L’arithmétique des entiers subit donc une double transformation : on en abstrait tout d’abord l’aspect formel au moyen d’une axiomatique sans contenu et on recode ces signes ininterprétés, simples signes sur le papier, sous forme de nombres. […] C’est par ce biais que l’axiomatique formelle peut devenir un calcul formel et qu’une passerelle peut être construite entre la théorie de la démonstration et la théorie de l’arithmétique.»[17]

Turing et la notion de calcul

A Cambridge, en 1935, Turing avait suivi les cours du mathématicien Newman, chef de fil britannique de la topologie à l’époque. Celui-ci avait suivi le congrès de Bologne de 1928, et son cours était donné dans l’esprit du programme de Hilbert. Les cours de Newman marquèrent Turing, et notamment sur la question de Hilbert concernant la démontrabilité.

En effet, « les résultats de Gödel n’éliminaient pas la possibilité qu’il existât une manière de distinguer les assertions démontrables de celles qui ne l’étaient pas. Y avaient-il une méthode définie, ou, comme le dit Newman, un procédé mécanique permettant de déterminer si une proposition mathématique était démontrable ou non ? »[18] Et c’est ce « procédé mécanique » qui va stimuler l’esprit de Turing.

Gödel avait donc arithmétisé l’axiomatique formelle en transformant les formules en nombre, et en présentant le calcul arithmétique comme la procédure qui permettait au final de décider, de démontrer. Turing allait en quelque sorte redéfinir la notion intuitive de calcul, dans le cadre de la métamathématique, en utilisant le concept de machine infinie et abstraite, et en s’attaquant au problème de la calculabilité des nombres réels. En somme, Turing proposait une autre solution que Gödel (qui dira d’ailleurs que celle de Turing est plus élégante) en apportant un concept de la calculabilité au travers de sa machine. Sa machine va permettre ainsi rendre palpable, de manière simple, ce qu’est le calcul.

Ainsi, « l’équivalent formel donné par Turing à la notion intuitive de ‘calculable par algorithme’ peut s’exprimer sous la forme suivante : toute fonction pour laquelle on a réussi à trouver un algorithme doit être calculable par une ‘machine’ d’un certain type, dite ‘de Turing’. »[19]

Conclusion sur l’indécidabilité et l’intelligence artificielle

C’est par le biais du problème de la décision que le programme de Hilbert a finalement préparé l’intelligence artificielle. « Il n’y a en effet qu’un pas de l’idée de procédure finie, explicite, effective, à celle de procédure mécanique […] »[20] Et nous verrons la prochaine fois comment Turing a pensé et conceptualisé cette idée de procédure mécanique. Mais plus précisément, j’espère avoir montré également comment peut se nouer le développement de cette métamathématique selon Hilbert, avec cette idée importante du raisonnement sur des signes, des symboles, avec le développement de cette idée de machine intelligente. Un rêve qui, en se concrétisant de manière partielle durant la seconde guerre mondiale, va finir par alimenter les rêves les plus fous…

---

[1] Alan Turing, « Théorie des nombres calculables, suivie d’une application au problème de la décision », in La machine de Turing, Alan Turing, Jean-Yves Girard, Seuil, 1995.

[2] Hilbert, Nouvelle fondations des mathématiques, 1922, in Intuitionnisme et théorie de la démonstration, Vrin, 1992.

[3] Jean-Yves Girard, « Le champ du signe ou la faillite du réductionnisme », in Le théorème de Gödel, Ernest Nagel, James R. Newman, Kurt Gödel, Jean-Yves Girard, Seuil, 1989, p. 150 et 151.

[4] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 79.

[5] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 80.

[6] Michel Bourdeau, Pensée symbolique et intuition, PUF, 1999, p.41.

[7] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 55.

[8] Michel Bourdeau, Pensée symbolique et intuition, PUF, 1999, p.42.

[9] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 58.

[10] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 58 et p.59.

[11] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 59.

[12] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 60.

[13] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 59.

[14] Jacques-Alain Miller, « La logique de la cure du Petit Hans selon Lacan », in La Cause Freudienne n°69, p. 97.

[15] Jacques-Alain Miller, « La logique de la cure du Petit Hans selon Lacan », in La Cause Freudienne n°69, p. 99.

[16] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 61.

[17] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 57.

[18] Andrew Hodges, Alan Turing ou l’énigme de l’intelligence, Payot, 1983, 1988, p. 88.

[19] Jean Lassègue, Turing, Les Belles Lettres, 1998, p. 70.

[20] Michel Bourdeau, Pensée symbolique et intuition, PUF, 1999, p. 40.

mot(s)-clé(s) : complétude, consistance, décidabilité, démontrabilité, Hilbert, incomplétude, Jacques-Alain Miller, Jean Lassègue, Jean-Yves Girard, Kurt Gödel, Lacan, Michel Bourdeau, turing

You can leave a response, or trackback from your own site.