L’article de Turing (1936) : une révolution dans les mathématiques, commentaire du § 1

Ce qui est connu aujourd’hui sous le nom de machine de Turing est exposé par Turing dans son article de « Théorie des nombres calculables, suivie d’une application au problème de la décision. (1936) »

Pour la question de la dialectique en mathématiques, du lien entre pensée et matière, donc pour des révolutionnaires marxistes, cet article est un des incontournables du XXème siècle.

Nous proposons donc une lecture commentée de l’article de Turing, phrase par phrase, dans le but de de clarifier les notions impliquées, puis les polémiques philosophiques qu’elles soulèvent. L’enseignement des mathématiques en France, très influencé par la vision positiviste du groupe Bourbaki, ignore complètement les notions révolutionnées par cet article.

Les camarades ayant fait des études scientifiques poussées en France, donc éloignées du travail manuel, seront donc peut-être ceux ayant le plus de mal à comprendre Turing, qu’ils n’hésitent donc pas à demander de explication aux camarades ayant une expérience pratique dans la mécanique.

Chaque titre en gras reprend une phrase de l’article de Turing.

On peut définir sommairement les nombres « calculables » comme étant des réels dont l’expression décimale est calculable avec des moyens finis.

La notion de nombre réel est la première un peu mystérieuse qu’un élève en math rencontre au collège ou au lycée. Les cours de maths donnent des noms à des nombres qu’on a rencontrés dans la vie : les « entiers » positifs puis négatifs 0, 1,2,3,-1,-2,-3 puis les « rationnels » qui sont des fractions d’entiers 1/2, 1/3, 3/4 etc. Les nombres racine de 2 et Pi qui n’apparaissent pas dans cette liste font partie des nombres courants (théorème de Pythagore, surface du cercle) mais ne sont ni « entiers » ni « rationnels ». D’un air gêné et mystérieux les professeurs parlent alors des nombres « réels », dont la construction ne peut être vue que dans l’enseignement supérieur. Premier mystère : les nombres réels semblent très éloignés de la réalité !

Turing évoque un ensemble, celui des nombres « calculables » qui est très peu familier a l’étudiant en maths, n’apparaît pas dans nos manuels, sans doute parce que c’est un anglais qui a fait cette découverte majeure, pas un français. On voit par cela même que ceux qui écrivent ces manuels font des choix très subjectifs. L’article de Turing va montrer définitivement que les nombres réels n’ont rien de réel.

Par réels dont l’expression décimale est calculable avec des moyens finis il entend la chose suivante : donnez-moi n’importe quel rang, je calculerai la décimale de ce rang-là du nombre en question.

Par exemple l’entier 4 est calculable : il s’écrit 4,0000.... et si on nous demande sa première décimale, on répond 4, la deuxième, on répond 0, la troisième, on répond 0, et le lecteur non spécialiste peut répondre si on lui demande la millionième décimale : 0. Le petit texte suivant est ce que Turing entend par « moyen fini » pour décrire 4 : le premier chiffre est 4 et après la virgule tout chiffre est 0.

Un rationnel comme 1/3 est aussi constructible : comme 1/3=0,3333... on peut donner immédiatement la première décimale : 0 puis la deuxième, troisième car elles valent toutes 3. Le petit texte suivant est un « moyen fini » pour décrire 1/3 : le premier chiffre est 0 et après la virgule tout chiffre est 3.

Bien sûr si on veut écrire toutes les décimales on devra écrire infiniment des zéros dans le premier cas, des trois dans le deuxième cas, cela prendra un temps infini, mais pour chaque décimale, on a besoin d’un temps fini : celui de lire la recette et de l’appliquer. Donc ces nombres même avec une infinité de décimales sont constructibles par des moyens finis.

Pour 1/7=0.142857 142857 .... qui comme toutes les fractions d’entiers (écrit dans toute base autre que la base 10) a des décimales qui à partir d’un certain rang se répètent périodiquement, on aura une recette plus longue mais toujours finie.

On peut montrer que les nombres non rationnels racine de 2 et Pi sont également calculables, même si leur écriture décimale n’est pas périodique.
Et cela est fondamental : ces nombres qui sont différents des fractions d’entiers si on adopte la distinction rationnels/irrationnels, ne le sont plus si on adopte la division calculables/non calculables.

Donc quand à l’école on nous parle de l’ensemble des « réels » comme l’ensemble assez grand pour contenir ces deux nombres sans lesquels on ne fait ni maths ni physique, on nous cache l’existence d’un ensemble autre : celui des nombres « calculables ». On s’en tient aux maths de l’antiquité grecque qui furent effrayés par les nombres « irrationnels »

En lieu et place des nombres calculables , j’aurais pu tout aussi bien définir et étudier les fonctions calculables d’une variable entière, réelle ou calculable, les prédicats calculable, et ainsi de suite. Dans tous les cas les enjeux fondamentaux restent les mêmes , et j’ai donc choisi de traiter ici explicitement les nombres calculables, qui font intervenir les techniques les moins lourdes.

Autre notion révolutionnaire derrière cette phrase anodine : démontrer des propriétés de calculabilité sur des nombres ou des prédicats revient au même. Mais ce n’est pas Turing qui fait la révolution, il ne fait que se placer dans le nouveau monde créé par Gödel :

Les problèmes des fondements des mathématiques posés depuis la crise de la géométrie non euclidienne au XIX ème siècle ont fait naître une nouvelle branche de la science : la méta-mathématique : les preuves des résultats des mathématiques deviennent eux-mêmes des objets qu’on étudie. Mais c’est un domaine bien séparé. Frege, le grand mathématicien fondateur moderne de ce domaine (après les essais d’Aristote, Leibniz, Boole) est un réactionnaire très antisémite et conservateur, anti-Hegelien. Mais Godel vers 1930 a montré que ces domaines ne sont pas séparés du tout ! les nombres qu’il a introduits font le lien entre ces deux domaines. Turing ne fait qu’entériner ce résultat. Il ya une seule substance disait Spinoza, c’est aussi vrai en mathématiques.

Là encore cette notion déjà conçue comme un acquis par Turing n’a jamais été intégrée par Bourbaki. Un de ses porte-parole Jean Dieudonné dans son livre « Pour l’honneur de l’esprit humain », chapitre « Problèmes et pseudo-problèmes de fondements » continue même après Gödel à soutenir que les mathématiques et les métamathématiques sont deux domaines distincts, que la logique ne fait pas partie des mathématiques : les mathématiciens ne connaissent guère ce que font les logiciens et ne leur accordent pas plus d’attention qu’à des sciences très éloignées des mathématiques, comme la biologie ou la géologie

Lorsque Turing suit Gödel en rappelant que calculer sur des prédicats (domaine de la logique, méta-mathématique) ou de nombre (mathématiques) est la même chose, on voit que le philosophe J. Dieudonné contredit un acquis des mathématiques et de la logique que le mathématicien J. Dieudonné a très bien compris (dans le livre cité p.244 quand il écrit que les axiomes de ZF entrainent ceux de Peano etc).

Certes cette notion ne parût pas évidente à de nombreux mathématiciens, qui ne pouvaient à cause de leur point de vue philosophique accepter les résultats d’incomplétude de Godel. L’anticipant sans doute, Turing promet :

J’espère publier sous peu un article concernant l’étude des relations entre nombres calculables, fonctions, etc. J’y développerai une théorie des fonctions d’une variable réelle, revue dans la perspective de la calculabilité

En fait Turing n’eut pas besoin de le faire car les idées de Godel avaient définitivement largement triomphé, alors que Godel lui-même avait eut peur de les clamer trop haut pour ne pas choquer.

Selon ma définition, un nombre est calculable si sa représentation décimale peut être écrite par une machine

Cette phrase qui peut paraître anodine est une révolution pour l’époque : les ordinateurs n’existent pas, donc Turing parle de machine d’une façon très abstraite. Son article va présenter ce qu’il entend par machine, ce n’est pas du tout un modèle d’ordinateur, mais un modèle de notre cerveau en action. Il ne fait pas des maths du point de vue d’un esprit pur détaché de la matière, mais d’une machine (machine de Turing)

Si notre cerveau est une machine de Turing, où est passée notre âme ? nous n’en avons pas !

Le point de vue révolutionnaire est donc qu’il aborde les nombres non du point de vue d’un cerveau idéalisé qui peut manipuler les concepts liés à l’infini sans savoir s’ils existent depuis Cantor, mais en étudiant quelles mathématiques on peut construire en modélisant nos raisonnements par un outil mécanique.

Cela annonce la réponse positive à la question : les ordinateurs peuvent-ils penser ? posée dans son futur article « Les ordinateurs et l’intelligence (1950) », car dans le présent article le cerveau mathématique est modélisé par une machine.