Le concept de hasard intrigue depuis longtemps les physiciens, et même l'humanité en général. Quelle est l'origine du hasard ? Dans quelle mesure le futur peut-il être prédit ? Notre incapacité à prédire l'avenir est-elle la conséquence de nos limites humaines ou plutôt la conséquence d'une impossibilité de principe ? Ces questions ont, en physique, une longue histoire. La physique classique héritée d'Isaac Newton était complètement déterministe : la connaissance parfaite de l'état d'un système à un instant donné permettait en principe la détermination de son état à tout instant ultérieur. Puis vint au début de ce siècle la mécanique quantique, où probabilités et hasard interviennent au niveau le plus fondamental de la théorie ; en effet, celle-ci ne peut fournir que des probabilités de mesurer telle ou telle valeur de la position, de l'énergie, etc. La mécanique quantique introduisit donc une indétermination fondamentale dans la nature, chose qu'Einstein lui-même ne voulut jamais accepter, comme en témoigne son célèbre « Dieu ne joue pas aux dés ». Puis, assez récemment, on s'aperçut avec l'étude des « systèmes dynamiques », qu'après tout, la physique classique avait aussi du hasard, ou plus exactement de l'imprévisibilité, enfouis en son sein, puisque certains systèmes même très simples, comme un système de pendules, peuvent exhibir un comportement imprévisible (voir « Le chaos déterministe » dans La Recherche d'octubre 1990). Le hasard, souvent associé au désordre, est ainsi devenu, du moins en physique, une notion pleine de contenu.
Et en mathématiques, discipline souvent perçue comme la certitude par excellence ? Le hasard y a-t-il une place ? La question est déjà un peu surprenante. La réponse l'est encore plus ! Différents travaux, notamment les miens, ont montré que la situation en mathématiques est apparentée à celle qui prévaut en physique : le hasard apparaît en mathématiques à un niveau fondamental. Je ne fais pas ici allusion à la théorie des probabilités, qui fait partie intégrante des mathématiques et qui est un outil pour décrire et étudier des phénomènes aléatoires, sans se préoccuper de l'origine de leur caractère aléatoire. La problématique qui nous occupe ici est tout autre et, d'un certain point de vue, beaucoup plus profonde : supposons que nous, mathématiciens, n'arrivions pas à démontrer un théorème, que nous ne discernions pas une structure ou une loi portant sur des nombres ou d'autres entités (cela arrive très souvent, et même dans la plupart des cas !). Plusieurs questions sont alors possibles : est-ce de notre faute, est-ce parce que nous ne sommes pas assez astucieux, parce que nous n'avons pas assez travaillé ? Ou bien est-ce plutôt parce qu'il n'y a pas de loi mathématique à trouver, pas de théorème, pas de réponse à la question mathématique que nous nous sommes posée ? C'est en liaison avec cette dernière question, comme nous le verrons, qu'apparaissent les thèmes du hasard et de l'imprévisibilité en mathématiques.
Une façon d'orienter notre réflexion sur cette question est de nous rappeler la célèbre liste des vingt-trois problèmes que le mathématicien allemand David Hilbert (fig. 1) avait proposée en 1900 en tant que défi au XXe siècle naissant(1). L'un des problèmes, le sixième de la liste, était d'axiomatiser la physique, c'est-à-dire d'exprimer toutes les lois fondamentales de la physique sous forme de règles mathématiques formelles ; cette question englobait l'axiomatisation de la théorie des probabilités car, pour Hilbert, les probabilités concernaient le monde réel et étaient donc du ressort de la physique. Son dixième problème avait rapport, lui, aux équations « diophantiennes », c'est-à-dire les équations algébriques où l'on cherche des solutions sous forme de nombres entiers. La question posée par Hilbert était : « Y a-t-il un moyen de décider si une équation algébrique possède ou non une solution en nombres entiers ? ». Hilbert était loin de soupçonner une quelconque relation entre ces deux problèmes, alors que nous verrons plus loin qu'il y en a bel et bien une.
Comment en est-on arrivé là ? Un premier point a rapport avec la notion de raisonnement axiomatique, c'est-à-dire de raisonnement mathématique fondé sur des règles formelles. Le système géométrique d'Euclide est un exemple simple de système axiomatique, mais depuis la fin du XIXe siècle divers systèmes d'axiomes ont été proposés afin de formaliser complètement les mathématiques ainsi que la logique sur laquelle tout raisonnement humain repose. L'axiomatique et le fondement des mathématiques ont été étudiés par de nombreux chercheurs, y compris par Hilbert lui-même. En particulier, ce dernier avait formulé une exigence : pour qu'un système d'axiomes soit satisfaisant, il doit exister une « procédure mécanique », c'est-à-dire une suite d'opérations logiques en nombre fini, permettant de décider si une démonstration mathématique quelconque vérifie ou non les règles formelles fixées. C'est là une exigence de clarté et d'objectivité, qui semble parfaitement naturelle. Le point important pour la suite est que si l'on bâtit un système d'axiomes cohérent (c'est-à-dire tel qu'on ne peut y prouver un résultat et son contraire simultanément) et complet (c'est-à-dire tel que toute assertion y est soit vraie, soit fausse), alors il découle immédiatement qu'il existe une procédure mécanique permettant --- en principe --- de trancher toute question qui puisse être formulée dans le cadre de cette théorie.
Une telle procédure consisterait (du moins en principe, car en pratique le temps nécessaire serait prohibitif) à faire la liste de toutes les démonstrations possibles écrites dans le langage formel, c'est-à-dire dans le système d'axiomes choisi, par ordre de taille et par ordre alphabétique des symboles employés. C'est ce qu'on peut appeler de manière imagée l'« algorithme du British Museum », pour faire allusion au gigantisme de l'« inventaire » à effectuer. Autrement dit, on énumère toutes les démonstrations possibles, et on vérifie si elles découlent bien des règles formelles du système axiomatique. De cette façon, on obtient en principe tous les théorèmes, tout ce qui peut être prouvé dans le cadre du système d'axiomes. Et si celui-ci est cohérent et complet, toute affirmation pourra être confirmée (si elle est démontrée) ou infirmée (son contraire est alors démontré). Ainsi, cela fournit une procédure mécanique permettant de décider si une assertion est vraie ou non.
Malheureusement, la situation s'est avérée beaucoup moin simple. On sait, depuis les travaux fondamentaux de l'Autrichien Kurt Gödel en 1931 et du Britannique Alan Turing en 1936 (fig. 2), que cette entreprise est vaine : il n'existe pas de système axiomatique cohérent et complet pour l'arithmétique, et de plus il ne peut y avoir de procédé mécanique permettant de déterminer, pour toute assertion mathématique, si elle est vraie ou fausse.
De ce résultat qui a profondément marqué la pensée mathématique, Gödel a fourni une très ingénieuse démonstration : c'est son célèbre « théorème d'incomplétude ». Mais l'approche de Turing me semble, d'une certaine manière, plus fondamentale et plus facile à comprendre. Je me réfère ici au théorème de Turing, affirmant qu'il n'existe pas de procédure mécanique pouvant déterminer, pour un programme informatique arbitraire, s'il s'exécutera en un temps fini ou non une fois mis en route. Le théorème d'incomplétude de Gödel en découle immédiatement : s'il n'existe pas de procédure mécanique pour déterminer si un programme s'arrête en un temps fini ou non, alors il ne peut non plus exister de système d'axiomes permettant de le faire.
Examinons maintenant la situation à laquelle on aboutit. Le nombre N est l'essentiel de l'information incluse dans le programme (P) que l'on vient de décrire. Par conséquent, la taille de ce programme est de l'ordre de log2 N bits, puisque pour exprimer le nombre N, il n'est besoin que de log2 N bits dans le système binaire (par exemple, le nombre 109 s'écrit 1101101 dans le système binaire, ce qui nécessite donc 7 ≈ log2 109 bits). Bien sûr, le programme (P) doit aussi contenir d'autres instructions permettant d'énumérer et de simuler l'exécution de tous les programmes de taille inférieure à N bits, mais le résultat n'est pas fondamentalement modifié : le programme (P) a bien une taille d'ordre log2 N bits (donc inférieure à N bits). Ce point nécessite peut être un peu plus d'éclaircissements : naïvement, on aurait tendance à penser que (P) doit contenir en lui tous les programmes de moins de N bits. Mais ce n'est pas parce que (P) simule leur exécution qu'il doit les contenir ! Pour donner une image, un programme chargé d'effectuer la somme de tous les entiers de 1 à 1 000 n'a pas besoin de contenir en mémoire tous les entiers de 1 à 1 000 : il les produit successivement au fur et à mesure du calcul de la somme. Cela pour faire comprendre que N est bien l'ingrédient principal du programme (P). Mais revenons à notre propos ; par construction, ce programme produit un résultat qui est au moins deux fois plus grande que celui produit par tout programme dont la taille est inférieure à N bits : il y a contradiction, puisque (P) fait lui-même partie de ces programmes et qu'il donnerait donc un résultat au moins deux fois plus grand que celui qu'il fournit lui-même... L'hypothèse de départ (l'existence de (P)) est alors fausse. Le problème de l'arrêt d'un programme est donc insoluble, ce que nous venons de montrer en utilisant un point de vue de la théorie de l'information.
Partons de ce résultat fondamental de Turing ; afin d'obtenir mon résultat établi en 1987(2) sur le hasard en mathématiques, il suffit de modifier le vocabulaire. C'est une sorte de calembour mathématique. De l'insolubilité du problème de l'arrêt, on passe au hasard lié à la probabilité d'arrêt. Qu'est donc cette dernière ? Au lieu de se demander si un programme donné va s'arrêter ou non au bout d'un temps fini, on considère l'ensemble de tous les programmes informatiques possibles, ce qui peut se faire en principe à l'aide d'un ordinateur idéalisé, appelé dans le jargon « calculateur universel de Turing ». A chaque programme possible, on associe une probabilité (à ne pas confondre avec la probabilité d'arrêt que l'on va bientôt définir). Comme tout programme est finalement équivalent à une suite de bits, on choisit chaque bit au hasard, par exemple en tirant à pile ou face : à un programme de N bits on associera donc la probabilité 1/2N. En fait, on se limite aux programmes bien structurés dont on suppose qu'ils se terminent par l'instruction « fin de programme », laquelle ne peut apparaître en début ou en milieu de programme ; autrement dit, aucun programme bien structuré ne constitue l'extension d'un autre programme bien structuré. Cette hypothèse est technique mais essentielle, car en son absence le total des probabilités 1/2N serait supérieur à 1 (et même infini). On définit alors la probabilité d'arrêt Ω (oméga) : c'est la probabilité pour que, ayant tiré au hasard un programme, celui-ci s'exécute en un nombre fini d'étapes. Ce nombre Ω vaut ∑N (aN / 2N), où aN est le nombre de programmes bien structurés de N bits qui s'exécutent en un temps fini. Ω est une probabilité, donc un nombre compris entre 0 et 1 ; si l'on trouvait Ω = 0, cela signifierait qu'aucun programme ne s'arrête, et si l'on trouvait Ω = 1, qu'ils s'arrêtent tous. Cette probabilité peut être exprimée en diverses bases ; une base particulièrement commode est la base binaire, dans laquelle le nombre Ω est une suite de 0 ou 1, par exemple 0,111010001101.... La question que l'on peut alors se poser est : « Quel est le N-ième bit de la probabilité d'arrêt Ω ? »
L'assertion de Turing (« le problème de l'arrêt est indécidable ») mène à mon résultat établissant que la probabilité d'arrêt est aléatoire ou plus exactement constitue de l'information mathématique irréductible. En d'autres termes, chaque bit de la représentation binaire de Ω est un fait mathématique qui est logiquement et statistiquement indépendant des autres : savoir si un bit donné de Ω est un 0 ou un 1 est un fait mathématique irréductible, qui ne peut être davantage condensé ou réduit. Une manière plus précise de le dire est que la probabilité d'arrêt est algorithmiquement aléatoire, c'est-à-dire que pour calculer N bits de la représentation binaire de Ω, il faut un programme informatique dont la taille est d'au moins N bits (voir l'encadré 1). Une façon résumée d'exprimer cela est : « L'assertion que le N-ième bit de Ω est un 0 ou un 1, pour un N donné, est un fait mathématique aléatoire, analogue au résultat d'un jet de pile ou face ».
On rétorquera immédiatement que ce n'est pas le genre d'assertions que l'on rencontre habituellement en mathématiques pures. On aimerait bien pouvoir traduire cet énoncé dans le langage de la théorie des nombres, laquelle constitue le soubassement des mathématiques. En fait, Gödel était confronté au même problème. L'assertion vraie mais indémontrable qu'il avait construite était bizarre, elle disait : « je suis indémontrable ! ». Gödel a déployé énormément d'ingéniosité et utilisé des raisonnements très sophistiqués afin de transformer « je suis indémontrable » en un énoncé portant sur les nombres entiers. Les travaux de Gödel ont donné lieu à de nombreuses recherches, dont la conclusion finale est que le dixième problème d'Hilbert est insoluble : il n'existe pas d'algorithme pouvant déterminer, en un nombre fini d'opérations, si une équation diophantienne arbitraire possède une solution. En fait, ce problème s'avère équivalent à celui de Turing sur l'arrêt d'un programme : étant donné un programme informatique, on peut construire une équation diophantienne qui a une solution si et seulement si ce programme s'exécute en un temps fini ; réciproquement, étant donnée une équation diophantienne, on peut construire un programme qui s'arrête si et seulement si cette équation possède une solution.
Particulièrement spectaculaires sont dans ce contexte les travaux des mathématiciens James P. Jones, de l'université de Calgary au Canada, et Yuri V. Matijasevic, de l'institut Steklov à Léningrad, publiés il y a environ six ans(3). Ces deux mathématiciens ont remarqué qu'il existait un théorème très simple, démontré par le Français Edouard Lucas, il y a plus d'un siècle, et qui résoud le dixième problème de Hilbert assez facilement s'il est utilisé de façon appropriée. Le théorème de Lucas concerne la parité des coefficients du binôme : demandons-nous si le coefficient de XK dans le développement de (1+X)N est pair ou impair, c'est-à-dire quelle est la parité du K-ième coefficient binomial d'ordre N (pour K = 0, 1, 2,..., N) ; le théorème de Lucas répond que ce coefficient est impair si et seulement si « K implique N en tant que suites de bits ». Cela signifie que ce coefficient est impair si à chaque « 1 » de la représentation binaire de K correspond un « 1 » à la même place dans la représentation binaire de N (fig. 3). Dans le cas contraire, le coefficient binomial est pair.
En utilisant la technique de Jones et Matijasevic (voir l'encadré 2), qui se fonde sur ce remarquable théorème de Lucas, j'ai mis au point un ensemble de programmes, écrits dans le langage C (et très récemment, dans le langage SETL2(4)), et que j'ai fait « tourner » sur un ordinateur IBM RISC System/6000 (les lecteurs intéressés par le logiciel peuvent me contacter(5)). Pour obtenir quoi ? Une équation diophantienne, plus exactement une équation diophantienne exponentielle. Les équations de ce type ne comportent que des additions, des multiplications et des exponentiations, les constantes et les inconnues considérées étant des nombres entiers positifs ou nuls. Contrairement à une équation diophantienne classique, on admet que la puissance à laquelle est élevée une inconnue puisse être aussi une inconnue. Ainsi, par exemple, une telle équation peut contenir non seulement des termes comme X2 ou X3, mais aussi des termes comme XY ou YX.
L'équation diophantienne que j'ai obtenue comporte près de 17 000 variables et occupe plus de 200 pages (voir « Une extension spectaculaire du théorème de Gödel : l'équation de Chaitin » dans La Recherche de juin 1988) ! Quelle est sa signification ? Elle contient un paramètre unique, le nombre N. Pour toute valeur donnée de ce paramètre, posons-nous la question suivante : « Cette équation a-t-elle un nombre fini ou infini de solutions en nombres entiers (c'est-à-dire un nombre fini ou infini de listes de 17 000 nombres entiers, chaque liste étant une solution de l'équation) ? ». La réponse à cette question s'avère être un fait arithmétique aléatoire, analogue à un tirage à pile ou face. Elle est une transcription arithmétique du fait mathématique irréductible que le N-ième bit de la probabilité d'arrêt Ω est 0 ou 1 : si cette équation diophantienne (de paramètre N) a un nombre fini de solutions, alors ce N-ième bit est 0, et si l'équation possède un nombre infini de solutions, ce bit est 1 (soulignons en passant que s'il n'y a pas de solution, le nombre de solutions est fini et vaut 0). La réponse à la question ne peut donc pas être calculée, et le N-ième bit de Ω non plus. Cela ne veut pas dire que les bits de Ω ne sont pas définis et déterminés mathématiquement, mais plutôt qu'il n'existe pas d'algorithme à nombre fini d'étapes pour les calculer, et que la connaissance des N premiers bits de Ω n'aide strictement en rien à la détermination des suivants.
La différence par rapport au problème posé par Hilbert est double ; d'une part, Hilbert ne pensait qu'aux équations diophantiennes classiques, non exponentielles ; d'autre part, la question qu'il avait posée était : « Y a-t-il une solution à l'équation ? » Cette question est indécidable, mais la réponse n'est pas totalement aléatoire, elle ne l'est que dans une certaine mesure. Les réponses ne sont pas indépendantes les unes des autres ; en effet, on sait qu'étant donné un nombre fini d'équations diophantiennes, il est possible de déterminer lesquelles ont une solution si l'on sait combien d'entre elles en possèdent. Pour obtenir un hasard vraiment total, semblable à celui associé à un tirage à pile ou face, la question adéquate que l'on doit poser est : « Y a-t-il un nombre fini ou infini de solutions ? » Mon assertion est que l'on ne pourra jamais le savoir, car décider si le nombre de solutions est fini ou infini, pour chaque valeur de N, est un fait mathématique irréductible. La réponse est, au sens algorithmique, aléatoire. La seule façon d'aller de l'avant est de considérer les réponses comme des axiomes. Si l'on cherche à résoudre M fois la question de savoir si le nombre de solutions est fini pour M valeurs données du paramètre N, alors il faudra incluire M bits d'information dans les axiomes de notre système formel. C'est en ce sens précis que l'on peut dire que les mathématiques contiennent du « hasard ».
Cela fait maintenant près d'un siècle que la philosophie et les fondements des mathématiques suscitent un grand intérêt. Auparavant, de nombreux efforts ont été consacrés à rendre rigoureuse l'analyse mathématique (la notion de nombre réel, de limite, etc.). L'examen moderne des mathématiques a réellement débuté, je pense, avec la théorie de l'infini de G. Cantor et les paradoxes et les surprises qu'elle a engendrés, et avec les efforts fournis par des mathématiciens comme Peano, Russell et Whitehead pour donner aux mathématiques des fondements solides et rigoureux. On avait placé beaucoup d'espoir en la théorie des ensembles. On avait ainsi cherché à définir de façon rigoureuse les nombres entiers 0, 1, 2, 3,... en termes d'ensembles. Mais il s'est avéré que la notion d'ensemble peut engendrer toutes sortes de paradoxes (Bertrand Russell en a donné un exemple célèbre : « L'ensemble de tous les ensembles qui ne font pas partie d'eux-mêmes » ; cet ensemble fait-il partie de lui-même ?). La théorie des ensembles est une partie fascinante et vitale des mathématiques ; néanmoins il me semble qu'il y a eu un certain désabusement vis-à-vis d'elle et qu'un retour aux 0, 1, 2, 3,... intuitifs s'est opéré. Malheureusement, les travaux que j'ai mentionnés, et en particulier mon propre travail, font que l'édifice des nombres entiers paraît moins solide qu'on ne le pensait. J'ai toujours cru, et probablement la plupart des mathématiciens y croient aussi, en un sorte d'univers platonicien où règne une « réalité mathématique » indépendante de la réalité physique. Ainsi, la question de savoir si une équation diophantienne a un nombre fini ou infini de solutions a très peu de sens concret, mais j'ai toujours pensé en mon for intérieur que même si nous ne pourrons jamais y répondre, Dieu, lui, le pouvait.
Avec ces découvertes, les mathématiciens sont en train de rejoindre, en un sens, leurs collègues de la physique théorique. Ce n'est pas nécessairement une mauvaise chose. Dans la physique moderne, le hasard et l'imprévisibilité jouent un rôle fondamental ; la reconnaissance et la caractérisation de ce fait, lequel pouvait être perçu a priori comme une limitation, sont un progrès. J'ai la conviction qu'il en sera de même en mathématiques pures.
Gregory J. Chaitin travaille au centre de recherches Thomas J. Watson d'IBM à Yorktown Heights aux Etats-Unis. Ses recherches ont trait à la théorie algorithmique de l'information, dont il a posé les bases vers le milieu des années 1960.
(2) G.J. Chaitin, Advances in Applied Mathematics, 8, 119, 1987; G.J.Chaitin, Algorithmic information theory, Cambridge University Press, 1990 (troisième impression).
(3)
J.P. Jones et Y.V. Matijasevic, Journal of Symbolic Logic,
49, 818, 1984.
(4)
SETL2 est un nouveau langage de programmation, permettant
d'écrire ces programmes de façon plus courte et plus
facile à comprendre (mais ils sont plus lents). Ce langage se
fonde sur un idée de J.T.Schwartz de l'institut Courant
à New York, selon laquelle la théorie des ensembles peut
être convertie directement dans un langage de programmation
(voir W.K. Snyder, The SETL2 programming language, Courant
Institute, 1990; J.T. Schwartz et al., Programming with sets --- An
introduction to SETL, Springer-Verlag, 1986).
(5)
G.J. Chaitin,
LISP for « Algorithmic information theory » in
C, août 1990.
Qu'est-ce qu'un nombre normal ? Un nombre est dit normal dans une base
b si chacun des b chiffres possibles apparaît,
dans le développement du nombre selon cette base, avec la
même fréquence 1/b, si chacun des
b2 groupes de deux chiffres successifs
apparaît avec la même fréquence
1/b2, et de même avec les groupes de trois
chiffres, de quatre chiffres, etc. Par exemple, un nombre est normal
dans le système binaire (b = 2) si dans son
développement binaire les chiffres 0 et 1 apparaissent avec las
même fréquence limite 1/2, si les séquences 00,
01, 10, 11 apparaissent avec la même fréquence limite
1/4, etc. Un nombre est dit absolument normal s'il est normal
quelle que soit la base b dans laquelle il est exprimé.
E. Borel montra en 1909 que presque tous (expression qui a un
sens mathématique précis) les nombres réels sont
absolument normaux. En d'autres termes, choisissons un nombre en
tirant à pile ou face chacun de ses bits constituant son
développement infini dans le système binaire. Alors, le
nombre compris entre 0 et 1 choisi de cette façon est
absolument normal, et cela « presque sûrement »,
c'est-à-dire avec une probabilité égale à
1.
Si la non-normalité est l'exception à la règle,
on serait tenté de penser qu'il est facile de trouver des
exemples de nombres normaux. Qu'en est-il par exemple de
√2, π ou e ? Sont-ils normaux ? Chose
étonnante, on n'en sait rien ! De nombreux calculs par
ordinateurs ont été effectués afin d'obtenir les
chiffres successifs formant ces nombres et de déterminer leur
fréquence d'apparition ; tout se passe comme s'ils
étaient normaux, mais personne n'a pu à ce jour le
démontrer rigoureusement. En fait, il a été
extrêmement difficile d'exhibir un exemple de nombre normal. En
1933, D.G. Champernowne parvint à exhiber un nombre qu'il put
démontrer être normal dans le système
décimal ; ce nombre s'écrit :
Néanmoins, on dispose à présent d'un exemple
naturel de nombre absolument normal : la probabilitié
d'arrêt Ω dont il est question dans l'article. En
effet, on peut facilement démontrer que Ω est
absolument normal à partir du fait qu'il est algorithmiquement
aléatoire. Un nombre est algorithmiquement aléatoire
si, pour déterminer N bits de son développement
binaire, il faut un programme dont la taille est d'au moins N
bits. Pour donner un contre-exemple, les N décimales
des nombres 0,1111111111... ou 0,110110110110... peuvent être
calculés très facilement par un programme dont la taille
est très inférieure à N (pour N pas
trop petit) ; en effet, il suffit de traduire les ordres «
répéter N fois le chiffre 1 » ou «
répéter N' fois la séquence 110 » en
langage binaire. Ces nombres ne sont donc pas du tout
algorithmiquement aléatoires. Même si √2,
π ou e sont normaux (ce qui reste à prouver),
ils ne peuvent être algorithmiquement aléatoires,
puisqu'il existe des algorithmes de taille finie pour calculer leurs
chiffres successifs. Le nombre de Champernowne est même pire
à cet égard : non seulement ses chiffres sont
calculables et prévisibles, mais en plus il est très
facile de le faire. On voit donc clairement que la notion de nombre
algorithmiquement aléatoire est beaucoup plus forte que celle
de nombre normal. De la même façon, la grande importance
pratique des algorithmes produisant des nombres
pseudo-aléatoires (utilisés dans les jeux informatiques
ou dans certains méthodes de calcul numérique)
réside précisément dans le fait que les suites de
nombres produites sont extrêmement compressibles,
algorithmiquement parlant. (Cliché Harlingue-Viollet)
Mathématiquement, cela s'exprime ainsi : K « implique
» N si et seulement s'il existe des entiers positifs ou nuls
uniques b, x, y, z, u, v,
w tels que
Encadré 1. Les décimales de π forment-elles
une suite aléatoire?
En quel sens la suite de chiffres qui composent un nombre peut-elle
être qualifiée d'« aléatoire » ? La question est
moins simple qu'elle ne paraît. Il y a près d'un
siècle, le mathématicien français Emile Borel
(voir cliché) avait défini dans ce contexte la notion de
nombre « normal » et avait démontré que presque tous
les nombres sont normaux.
0, 0 1 2 3 4 5 6 7 8 9
10 11 12... 98 99 100 101 102...
998 999 1000 1001 1002....
Mais on ne sait pas si ce nombre est normal absolument,
c'est-à-dire normal dans toute base.
Encadré 2. Tirer à pile ou face à l'aide
d'une équation diophantienne
Comment traduire en équation algébrique la
détermination des bits de la probabilité d'arrêt
Ω dont il est question dans l'article ? La méthode
utilise une technique développée par Jones et
Matijasevic, qui elle-même s'appuie sur le
théorème de Lucas. Celui-ci affirme
(fig. 3)
que
K « implique » N bits à bit si et seulement si
le K-ième coefficient binomial d'ordre N est
impair. Jones et Matijasevic montrent que cela est équivalent
à dire que dans la base b = 2N, le
K-ième chiffre de 11N est impair.
b = 2N
Pour obtenir une équation diophantienne, il suffit de
réécrire ces cinq équations pour que leur membre
de droite soit 0, de les élever au carré et de les
ajouter. On obtient l'équation
(b+1)N = x bK+1 + y bK + z
z + u + 1 = bK
y + v + 1 = b
y = 2w + 1
[ b − 2N ]2 +
L'équation de 200 pages que j'ai obtenue a été
construite en utilisant de façon répétée
cette technique, afin d'exprimer en une équation diophantienne
le calcul du N-ième bit d'une K-ième
approximation de Ω. Cette équation possède
exactement une solution si ce bit est 1, et n'en possède pas si
ce bit est 0. On change alors le point de vue, et on considère
K non pas comme un paramètre mais comme une inconnue
supplémentaire. La même équation aura alors, pour
une valeur donnée du paramètre N, un nombre fini
ou infini de solutions selon que le N-ième bit de
Ω est 0 ou 1 (la valeur de K peut différer
d'une solution à l'autre). Pour K assez grand,
l'approximation de Ω est suffisament bonne pour que le
N-ième bit de la K-ième approximation de
Ω soit le bon. Mais il est impossible de calculer, pour
N donné, la valeur de K à partir de
laquelle le bit a la bonne valeur, car la probabilité
d'arrêt Ω est algorithmiquement aléatoire.
[ (b+1)N − x bK+1 − y bK − z ]2 +
[ z + u + 1 − bK ]2 +
[ y + v + 1 − b ]2 +
[ y − 2w − 1 ]2 = 0
Figure 1.
En 1900, lors d'un congrès tenu à Paris, le grand
mathématicien allemand David Hilbert (1862-1943) a
énoncé une liste restée célèbre de
23 problèmes ouverts. Ses travaux et ses réflexions ont
considérablement influencé les recherches
mathématiques du vingtième siècle. Son
dixième problème concernait la
résolubilité des équations diophantiennes :
existe-t-il une procédure permettant de déterminer en un
nombre fini d'opérations si une équation diophantienne
arbitraire possède une solution ? Y.V. Matijasevic a pu montrer
en 1970 que la réponse était négative. De
nombreux problèmes de mathématiques peuvent être
traduits en termes de non-résolubilité d'une certaine
équation diophantienne ; c'est le cas de la question si oui ou
non un programme informatique s'exécute en un temps fini.
(Cliché Bildarchiv Preussischer Kulturbesitz)
Figure 2.
Le logicien autrichien K. Gödel (1906-1978) (A) a
ébranlé en 1931 la conviction intime de la
quasi-totalité des mathématiciens, conviction selon
laquelle il était possible de construire des systèmes
formels d'axiomes qui soient complets et cohérents. Il a pu
démontrer que tout système formel comporte des
énoncés qui sont indécidibles,
c'est-à-dire qui ne peuvent être confirmés ou
infirmés en utilisant uniquement les axiomes du système.
Le Britannique A.M. Turing (1912-1954) (B) a formalisé les
notions de calculabilité et d'algorithmique qui sont les
fondements théoriques de l'informatique. Il a notamment
montré en 1936 qu'il n'existe pas de procédure
mécanique permettant de savoir si un programme arbitraire
s'exécutera en un temps fini ou non. (Clichés AFP et
E.T. ARCHIVE)
Figure 3.
Une programme informatique étant choisi au hasard, la
probabilité Ω pour qu'il s'exécute en un
temps fini peut s'écrire dans le système binaire sous
forme d'une suite de 0 ou 1, appelés bits. Pour obtenir une
équation déterminant les bits de la probabilité
d'arrêt d'un programme choisi au hasard, G.J.Chaitin a
utilisé des techniques qui s'appuient sur un
théorème simple dû à un
mathématicien français du siècle dernier, Edouard
A. Lucas (1842-1891). Ce théorème affirme que le
coefficient de XK dans le
développement de (1+X)N est impair si
et seulement si les « 1 » de l'écriture binaire de K
se retrouvent à la même place dans l'écriture
binaire de N.