Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 1
Origine et évolutions des architectures
Année 2002-2003

Suite N°4...

On découvrira un jour une méthode générale.
Il sera possible de réduire en elle toutes les données rationnelles à une sorte de calcul.
   Gottfried Leibniz - 1686

1.3.2 Note complémentaire sur l'origine des théories des années 1930

Les résultats de Gödel, Church, Turing et de nombreux autres ont au moins deux origines. La première est la recherche de ce que nous appelons l'algorithme universel; la seconde est une crise propre à la théorie des ensembles.
Nous allons dire quelques mots sur les deux.

Une origine lointaine : l'algorithme universel

Depuis toujours, les procédés de calcul faisaient l'objet d'un discours mathématique en langage clair. L'algorithme d'Euclide était décrit par un énoncé en langue naturelle.
La notation symbolique actuelle des nombres a été fixée au VII^e siècle par Brahmagupta, astronome indien et le zéro de position a été introduit [IFR94]. Plus tard, un ouzbeck de l'empire Sassanide, Al Khorizmi né en 783, donna la solution de l'équation du second degré et définit des règles de transformation d'expressions, c'est-à-dire une algèbre, à partir des travaux de Brahmagupta. Il écrivit une somme sur les procédés de calcul, qui sera traduite en latin et largement diffusée. On appellera dans la suite algorithme un procédé de calcul figurant dans cet ouvrage du nom de l'auteur. Plus tard on nommera algorithme tout procédé de calcul voire même tout raisonnement formel [DJE00].

Leibniz avait énoncé clairement la thèse de l'algorithme universel :
«Tout problème peut avoir une solution sous la forme d'un algorithme et de manière plus générale il existe un algorithme universel qui choisit automatiquement la méthode adaptée à la solution de tout problème».

L'idéologie mécaniste de Descartes, le déterminisme puis le positivisme aussi bien philosophiques que scientifiques ont fait croire à la vérité de cette thèse tout au long du XIX^e siècle, mais c'était implicitement que cette thèse était considérée comme vraie. La preuve de l'algorithme universel n'était pas la préoccupation première des mathématiciens.

La fin du XIX^e siècle

Cette fin de siècle voit plusieurs crises en matière de sciences. La première partie de la conclusion contient quelques détails sur ces crises et sur la façon dont les historiens des sciences les analysent.

La théorie des ensembles fondée par Georges Cantor date des années 1870 [CAV62]. Plusieurs autres mathématiciens Zermelo, Fraenkel, Dedekind entre autres, y contribuent. Zermelo écrit «La théorie des ensembles est la branche des mathématiques à laquelle il revient d'étudier mathématiquement les concepts fondamentaux de nombre, d'ordre et de fonction dans leur simplicité primitive, et par là de développer les bases logiques de l'arithmétique toute entière et de l'analyse» (cité dans [CAV62]). À la fin du siècle, elle est reconnue comme importante et prometteuse bien que, horreur mathématique, elle contient des paradoxes. Le premier est mis en évidence 1897. On l'aime ou on la déteste.David Hilbert est enthousiaste : «Personne ne nous chassera du paradis que Cantor a créé pour nous»ou «(cet édifice) représente une des plus belles créations de l'esprit mathématique». Weierstrass montre de la défiance. Kronecker est hostile, déclarant que Cantor est un corrupteur de la jeunesse. Henri Poincaré affirme «Les générations futures verront la théorie des ensembles comme la maladie que nous avons attrapée» et «La théorie des ensembles n'est pas stérile, elle produit des paradoxes». Plus radical, le mathématicien hollandais L.E. Brouwer crée l'école intuitionniste (on dit parfois constructiviste). Pour lui, les mathématiques doivent être limitées aux objets pour lesquels on a mis en évidence des méthodes pour les construire en un temps fini. Il abandonne ainsi les notions d'infini que certains nomment «mathématiques théologiques».

En 1902, Bertrand Russell (1872-1970), logicien britannique, longtemps plus tard prix Nobel de littérature en 1950, découvre plusieurs paradoxes.  Il publie en 1903, un ouvrage majeur «The principles of mathematics» ou «Principia mathematica», qui propose de nouveaux fondements aux mathématiques sous les espèces de la logique et de la théorie des ensembles. Il établit que les lois de base de l'arithmétique sont réductibles à des propositions de logique élémentaire. Puis, avec North Whitehead (1861-1947), son tuteur de l'époque, il entreprend d'appliquer ses théories aux mathématiques sous la forme de trois autres volumes de la Principia mathematica, publiés en 1910, 1912 et 1913.

Les paradoxes sont néanmoins toujours là. Voici l'un d'eux nommé paradoxe des catalogues, imaginé par Russel et Zermelo :

Un éditeur veut dresser le catalogue de tous les catalogues qui ne se mentionnent pas eux-mêmes. Il y figurera entre autres le catalogue des voyages en Aragon. Puisqu'un voyage en Aragon n'est pas un catalogue et qu'un catalogue n'est pas un voyage en Aragon, ce catalogue particulier ne se mentionne pas lui-même. En revanche, un catalogue des ouvrages imprimés se mentionne lui-même, puisqu'il est lui-même un ouvrage imprimé. Il n'appartient donc pas au catalogue que l'éditeur veut établir.

Le paradoxe tient aux réponses à la question : le Catalogue de tous les catalogues qui ne se mentionnent pas eux-mêmes doit-il se mentionner lui-même ?
.Si oui, il fait partie des catalogues qui se mentionnent eux-mêmes, il ne doit donc pas se citer.
.Si non, il appartient aux catalogues qui ne se mentionnent pas eux-mêmes et doit donc se mentionner.

Ce n'était pas le premier paradoxe logique. On connaissait depuis longtemps le paradoxe du menteur que Diogène Laerce attribuait à Eubulide, dialecticien de l'école grecque de Mégare.
Le crétois affirme : «Je suis un menteur». S'il l'est, en disant : «Je suis un menteur», il dit la vérité, donc il ne ment pas. Mais, s'il n'est pas menteur, ce qu'il dit est vrai. Or, il dit «Je suis un menteur», donc la vérité est qu'il ment.
Remarquons au passage que l'auteur étant grec, le menteur se trouve être crétois.

Le paradoxe du menteur amusait, le paradoxe de Russell angoisse les mathématiciens car il met en cause une théorie axiomatique. Remplaçons catalogue par ensemble et «se cite» par «appartient à», on arrive à : l'ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes.

Les paradoxes seront levés à la fin des années 1920 par Zermelo, Fraenkel et Neumann mais il faudra pour cela une modification de la théorie. On retrouvera une notion très voisine à propos du théorème de Gödel.

L'espoir d'une réponse

En 1900, un congrès international des mathématiciens est réuni à Paris pour la deuxième fois. David Hilbert (1862-1943), mathématicien allemand déjà cité, y présente un agenda de recherche, une collection de 23 problèmes à résoudre pendant le nouveau siècle. Hilbert continuera à travailler sur cette liste, la modifiant plusieurs fois.
Le second de ces problèmes a trait à la consistance des axiomes de l'arithmétique. L'auteur le placera en 1928 en 33^e position sous la forme de l'existence d'un algorithme pour déclarer vraie ou fausse une proposition logique, dans un système de logique assez puissant pour représenter les nombres naturels.

Hilbert demande ainsi que soit apportée la réponse définitive à l'existence de l'algorithme universel, c'est à dire l'existence d'un procédé de calcul permettant de résoudre sans réfléchir tout problème donné, reprenant ainsi la thèse de Leibniz et l'objectif de Joseph Gergonne en 1816. Il récrira cette proposition en 1928 sous une autre forme dite «décision de la décidabilité».

On peut présenter la chose en écrivant qu'il s'agit :

a) de convertir toutes les mathématiques existant en une théorie formelle, une variante de la théorie des ensembles devant lever les paradoxes;
b) de prouver la consistance de cette théorie formelle.

La tâche a) était considérée comme une affaire de peu de temps, le siècle précédent avait vu les grands succès de définitions formelles des fonctions, de la continuité, des nombres réels, l'axiomatisation de l'arithmétique, de la géométrie etc...

La tâche b) était nouvelle. Elle portait trois espoirs :

• l'absolue consistance de la preuve en mathématique;
• la perfection totale de la méthode axiomatique;
• la disparition du doute.

D. Hilbert trace un plan de recherche. En faisant abstraction du sens des symboles mathématiques, il s'agit de montrer qu'il existe une syntaxe, jeu des règles de liaison entre les symboles, cohérente et non contradictoire. On va étudier la mathématique elle-même comme objet et non plus seulement des objets mathématiques. Pour cela, il suffirait d'établir définitivement la liste des règles logiques avec lesquelles on fait des mathématiques de façon objective. Vue différemment, cette ambition est de mécaniser la production de théorèmes. On pourrait alors atteindre tous les résultats mathématiques en appliquant ces règles. On prétendrait aujourd'hui que l'ordinateur bien programmé peut produire tous les théorèmes.

Pour éviter les définitions en cercle vicieux, D. Hilbert pose des règles pour ce jeu. Elles consistent à admettre deux prémisses :
.les nombres entiers, dont l'axiomatique vient d'être établie par Péano et leurs propriétés élémentaires;
.l'emploi de règles logiques simples de manipulation de ces concepts.

Il nomme le tout «mathématiques réelles».
Il reste alors à démontrer que: «Tout résultat mathématique vrai est démontrable à partir des mathématiques réelles.»

L'idée directrice est de «projeter», mais comment?, les assertions logiques qui portent sur les mathématiques dans les mathématiques réelles et de démontrer qu'elles y sont vraies. Par exemple, si l'on trouvait une manière d'associer la proposition : «Les hommes sont mortels, Socrate est un homme, donc Socrate est mortel» à une égalité du type 2 x 3 = 6, on pourrait vérifier la justesse d'un raisonnement logique à travers des opérations des mathématiques réelles.

Le premier pas de la construction doit établir une relation cohérente entre les propositions logiques et les opérations sur les nombres. Si deux propositions logiques sont respectivement associées aux nombres m et n, la proposition logique liée à p (avec p = m+n ou p= m.n selon la règle de combinaison que l'on adopte) doit être la résultante des deux propositions précédentes.

Plusieurs mathématiciens construisent de tels systèmes dans les années 1920. Presburger publie en 1930 une procédure de décision applicable à une restriction de l'arithmétique. Il utilise l'addition et prouve que toutes ses propositions sont démontrables.

Kurt Gödel invente un système complet en 1931 et en démontre la cohérence [GOD01].

Les deux présentations que nous en faisons ci-après ne sont pas des exposés du travail de K. Gödel mais deux introductions successives pour être à même de comprendre la démarche suivie.

Première présentation de nature analogique.

Le raisonnement de K. Gödel est comparable au suivant :

1) Supposons qu’il existe une Théorie Complète (TC) fondée sur un nombre fini d'axiomes et par laquelle, si on considère une phrase quelconque, on pourra décider sans jamais se tromper si cette phrase est vraie ou non.

2) Considérons la phrase «TC ne dira jamais que la présente phrase est vraie».
Nommons cette phrase G, ce que nous noterons : G = «TC ne dira jamais que G est vraie».

3) Soumettons G à TC et demandons à TC si G est vraie ou non.

4) Si TC dit que G est vraie, alors G est fausse. Mais alors comme TC a dit que G était vraie, TC a commis une erreur. Cependant par hypothèse TC ne se trompe jamais, donc TC ne dira jamais que G est vraie.

5) Si «TC ne dira jamais que G est vraie» est vraie, d'après ce que nous venons de voir TC ne pourra jamais le dire.

6) Il ne peut donc pas exister de Théorie Complète, c’est-à-dire de théorie permettant, quelle que soit la phrase que l'on considère, de dire si elle est vraie ou non.

Deuxième présentation de nature analytique.

Première partie : on peut affecter un nombre à une expression logique.Il considère en premier un ensemble de signes et de lettres nécessaires à l'écriture des propositions. Ce sont Ì Ø Ù ( , ) x, y, z, P, Q, etc. Il affecte à chacun un nombre.
Le tableau ci-dessous est un exemple de jeu de dix signes, Gödel en utilisait 7.

signe	signification	nombre attaché
Ø	négation	1
$	il existe	2
Þ	implique	3
(	délimiteur gauche	4
)	délimiteur droit	5
=	égale	6
0	zéro	7
s	est le successeur de	8
,	séparateur	9
Ú	ou	10

Les signes que l'on a coutume d'utiliser n'y figurent pas tous :

• le signe Ù (et) qui équivaut à non ou;

les chiffres de l'arithmétique autres que le zéro, car tout nombre peut être construit à partir du nombre zéro et de la fonction successeur;le signe " , quel que soit, qui peut être remplacé par une combinaison de négation et de $.

• x, y, z numériques par les 3 premiers nombres premiers supérieurs à 10;
• p, q, r propositionnelles par les carrés des précédents;
• P, Q, R prédicatives par les cubes des premiers.

Dans la suite on ne distinguera plus signes et lettres.

Une proposition ou formule est écrite sous la forme de la concaténation de signes. On repère le rang du signe dans l'écriture. Gödel décide de le repérer dans la suite des nombres premiers. Le rang du signe sera le rang du nombre premier correspondant dans sa suite. Le couple formé par le signe et son rang (signe,rang) est alors traduit par un nombre unique contruit comme suit : prendre le nombre (premier) attaché au rang élevé à la puissance du nombre attaché au signe. La concaténation est traduite par le produit de ces nombres représentant les couples. À la fin des opérations, une formule est traduite par un nombre unique dit nombre de Gödel.

Cette construction du nombre associé à une formule est présentée sur l'exemple suivant :

Prenons la formule simple : ($ x)(x=s0) qui est interprêtable par «il existe un x successeur immédiat de 0».
Reprenons les valeurs des tableaux précédents. On construit le nouveau tableau :
 

(	$	x	)	(	x	=	s	0	)	signe
9	2	11	10	9	11	6	8	7	10	valeur
2	3	5	7	11	13	17	19	23	27	rang du signe repéré par la suite des nombres premiers
29	32	511	710	119	1311	176	198	237	2710	nombre unique résultant, pour chaque signe

Le nombre de Gödel de la formule est alors, en notant la multiplication par x :

($ x) (x = s0) ß 2⁹ x 3² x 5¹¹ x 7¹⁰ x 11⁹ x 13¹¹ x 17⁶ x 19⁸ x 23⁷ x 27¹⁰

Concaténer deux formules revient à combiner les nombres de Gödel de chacune en appliquant à nouveau la méthode précédente :

Prenons deux formules, la formule A et la formule B :

A est écrite ($ x)(x=s0) interprêtable par «il existe x successeur de 0». Soit m le nombre de Gödel de A.
B est écrite ($ y)(y=sx) interprêtable par «il existe y successeur de x». Soit n le nombre de Gödel de B.

La formule C : A ET B, interprêtable par «il existe x successeur de 0 ET il existe y successeur de x»
aura pour nombre de Gödel t construit en observant que
.la première formule a pour nombre m et a le rang 2 dans la liste des nombres premiers;
.la deuxième formule a pour nombre n et a le rang 3 dans la liste des nombres premiers.

On opérera ainsi de suite en utilisant chaque fois les notions de rang dans la liste des nombres premiers pour composer les propositions.

Note : Cette mise en relation établit s'il en était besoin que le champ des propositions n'est pas continu mais qu'il est potentiellement infini dénombrable.

Gödel a établi ainsi une fonction depuis l'ensemble des expressions d'un système axiomatique (signes, formules isolées, suite de formules) vers un sous ensemble des entiers.

On peut vérifier si un nombre est de Gödel en le décomposant en facteurs premiers. S'il l'est, on obtient la formule associée.
 

Toute proposition simple ou non est représentable par un nombre.

Deuxième partie : tout nombre entier a un nombre de Gödel.

Pour passer à l'écriture de formules arithmétiques et des nombres, il faut remplacer les variables x, y z par des nombres. Ces nombres seront écrits selon les formules qui les construisent.

Par exemple 5 = sssss0 (5 est le cinquième successeur de 0); 9 = sssssssss0 (9 est le neuvième successeur de 0).Le remplacement est faisable en un nombre fini d'opérations, même si la manipulation n'est pas aisée, ce dont on ne se préoccupe pas.

La numération de Gödel est une correspondance bijective  entre les expressions du calcul logique et un sous ensemble de N. Tout symbole, nombres entiers inclus, toute formule toute suite de formules possède un nombre de Gödel.

En résumé, on a obtenu le jeu de propriétés suivantes :
À tout nombre entier n quelconque, on associe une des interprétations suivantes :

• si n < 10, il lui correspond un symbole élémentaire,
• si n > 10, on considère sa décomposition (unique) en facteurs premiers :
• si n est un nombre premier supérieur à 10, ou son carré ou cube, il est le nombre d'un symbole de variable, de proposition ou prédicat selon la table de construction.
• Si n est le produit de nombres premiers successifs, c'est le nombre d'une formule ou d'une suite de formules selon les tables de construction.
• Sinon le nombre n'est pas un nombre de Gödel.

Troisième partie : une démonstration formelle a un nombre de Gödel.

On se donne une théorie sous la forme d'un jeu d'axiomes et de règles de substitutions valides. On construit ainsi, à partir des axiomes, des «formules» qui par leur origine même sont prouvées et ont le statut de théorèmes de la théorie. La suite des opérations qui mènent d'un axiome (ou de plusieurs) à la formule EST le raisonnement qui a été suivi.

Supposons que l'on ait deux énoncés. Le premier X est vrai. Le second F est démontrable à partir de X par une suite d'opérations de l'axiomatique dans laquelle on se trouve. On écrit :

«X étant vrai, la suite S de formules, dont les nombres sont x1, x2, etc.. est une preuve de la formule F dont le nombre est z.»

Gödel a montré que cette suite a elle même un nombre de Gödel. Ce nombre est noté Dem (X -> Y) ou démonstration de ce que X implique Y.

Réciproquement prouver qu'une assertion Z est fausse à partir de X a un nombre ØDem (X->Z) ou démonstration que X n'implique pas Z.

À ce point de la progression, l'espoir de Leibniz est comblé et le programme de Hilbert proche de l'achèvement car on peut toujours espérer que toute vérité logique sera prouvable et on détient un moyen de le prouver à l'intérieur des mathématiques réelles.

Quatrième partie : toute axiomatique au moins aussi puissante que l'arithmétique est incomplète*.

K. Gödel étudie dans l'arithmétique, la proposition logique particulière qui s'énonce comme suit :

«Il existe une proposition logique A, telle que ni A ni non-A ne peuvent être démontrées, et cela sans préciser A.»

Il montre alors successivement :

• que cette proposition a un nombre associé;
• que ce nombre est un nombre de Gödel valide;
• qu'ainsi cette proposition est vraie.

Plus généralement on dira que :
 
 

Dans toute axiomatique, au moins aussi puissante que l'arithmétique il existe au moins un énoncé mathématique vrai non démontrable par des moyens de nature finie.

Une conséquence est qu'un système d'axiomes tant soit peu complexe ne peut pas se fonder en lui-même.
Sa cohérence supposée ne peut être prouvée qu'en utilisant des assertions ou axiomes qui lui sont étrangers.

D. Hilbert cherchera sans la trouver la faille qui rétablirait l'ancienne thèse.

À ce point, il est bon de préciser que l'objectif final de D. Hilbert était d'établir que l'homme, le mathématicien pourrait établir par SON raisonnement, raisonnement humain, toute vérité mathématique. L'apport d'A. Turing est de faire réaliser cela non pas par un raisonnement humain mais par l'action d'une machine, certains disent même par le produit de forces de la nature puisqu'un ordinateur est un objet de la physique. Certes, ceci n'a pas grande importance directe pour l'informaticien, elle en a pour le philosophe. (cf. conclusion)

Venons en à la décidabilité. Le théorème de Gödel [GOD01] dit qu'il y a des énoncés non décidables, mais ne dit pas s'ils sont nombreux ou rarissimes. S'il y en avait beaucoup, les mathématiciens subodoraient qu'ils les auraient déjà rencontrées en nombre. Or la liste des conjectures, propositions que l'on croit vraies sans les avoir démontrées, augmentait assez régulièrement mais diminuait aussi au fur et à mesure des démonstrations depuis le début du XX^e siècle.

À part le grand théorème de Fermat, déjà ancien, peu de conjectures récentes résistaient longtemps. On pouvait donc à bon droit se dire que les propositions non démontrables ne se rencontraient jamais ou presque. Nombre de mathématiciens ont dédaigné le résultat étrange et abstrait de Gödel.

Peu à peu des problèmes indécidables ont été trouvés, en voici trois :

Le pavage du plan. On dispose de morceaux de papier aux formes géométriques variées non spécifiées et l'on convient d'en prendre au hasard quelques uns : peut-on savoir, a priori, c'est-à-dire sans connaître les morceaux de papier, si l'on va réussir à couvrir une surface, sans trou ni chevauchement? Ce problème est indécidable. En effet, il n'existe pas d'algorithme qui dira «c'est possible» ou «c'est impossible». En revanche, une fois déterminée la forme des morceaux de papier, on peut écrire un programme qui cherche exhaustivement la réponse.

La séquence qui n'est jamais parcourue. Un autre indécidable plus informatique a été découvert. Il n'y a pas de méthode qui décide a priori si un programme informatique possède une séquence qui ne sert jamais. Une conséquence établie récemment est que si un génome (pas nécessairement humain) est un programme, et il semble bien qu'il le soit, le séquencement complet du génome butera sur cette impossibilité. S'il existe des séquences inutiles, l'ordinateur ne pourra pas les trouver de façon systématique.

Le jeu de la vie. Plus immédiatement accessible est le jeu de la vie de John Conway, qui a servi plusieurs années comme base de travaux pratiques de méthodes de programmation au CNAM. Il est simple : on dispose au hasard sur un échiquier un nombre quelconque de pions. Puis on applique deux règles :

.si une case vide est entourée de trois pions, le coup d'après on y place un pion,
.si un pion a moins de deux ou plus de trois voisins, le coup d'après il est enlevé du jeu.Il a été démontré, dans les années 70, que son évolution est indécidable dans le sens suivant :
Il est impossible de prédire si, pour une configuration de départ quelconque, c'est-à-dire non précisée, il y aura extinction, alors tous les pions disparaîtront, ou s'il y aura survie éternelle, alors il restera toujours des pions. L'indécidabilité demeure si l'on complique le jeu avec des pions de divers types, ronds, carrés, triangulaires, etc. et des lois plus complexes. En supposant qu'on puisse simuler ainsi l'évolution des espèces animales, on ne peut pas dire vers quel destin s'acheminent les espèces. Pour obtenir une réponse, il faudra préciser les conditions initiales et pourquoi pas, laisser «tourner» l'ordinateur, attendant le résultat. En cliquant ici vous trouverez un jeu de Conway (annexe asi0013).
 

L'attention du lecteur est attirée sur le fait que l'indécidabilité n'est démontrée que pour des systèmes axiomatiques ou équivalents. Attribuer un caractère indécidable à des situations diverses non axiomatiques est une généralisation sans preuve.

Cet avertissement n'est pas une clause de style. On a lu d'innombrables billevesées sur ce sujet. Un exemple frappant est celui de Michel Serres qui affirme: «En appliquant donc le théorème de Gödel aux questions du clos et de l'ouvert touchant la sociologie, Régis Debray boucle et récapitule d'un geste l'histoire et le travail des deux cents ans qui précèdent». Michel Serres, Paris 1800, in Eléments d'histoire des sciences Bordas/Cultures, 1989, p. 359-360. L'annexe 15 contient le texte d'une conférence de Michel Bouveresse qui traite de ce sujet.

Cette restriction est, mutatis mutandis, de même nature que celle qui restreint l'application de la deuxième loi de la thermodynamique à des systèmes qui ne sont pas quelconques (cf. conclusion asi9995).

Au milieu des années 1930, on savait donc que l'algorithme universel ne pouvait pas exister et que des propositions non décidables pouvaient exister.

La non-contradiction de l'arithmétique a été prouvée par Gehrard Gentzen en 1937, mais évidemment pas au seul moyen de son axiomatique. Il a pour cela introduit une induction transfinie. Les mathématiciens en ont été un peu rassurés et de toute manière n'en ont pas empêchés de dormir.

On connaît aujourd'hui de nombreuses démonstrations du théorème de Gödel. Il est considéré comme parfaitement acquis et presque évident. On a montré qu'il est équivalent à l'insolubilité du problème de l'arrêt ainsi qu'au fait qu'il existe un problème récursivement énumérable qui n'est pas récursif.

Passons maintenant aux machines qui intéressent directement l'informaticien.