Connaissez-vous le nombre aléatoire Oméga de Chaïtin?
Gregory Chaitin est un mathématicien et informaticien et a son point de vue sur la notion formelle de hasard:
- Le hasard selon la définition de Chaitin correspond à un défaut de structure (pattern), et à une incompressibilité de l’information nécessaire pour le générer
(L’incomplétude est difficile à imaginer pour une suite finie de nombres, en effet, il est toujours possible de créer un algorithme générant cette suite finie. Par contre, concevoir un algorithme plus petit (codé avec moins de bits) que la suite elle-même n’est possible que pour un ensemble très restreint de suites de nombres. La complexité de Kolmogorov (nommée d’après le mathématicien Andreï Kolmogorov), est une mesure de cette compressibilité de l’information.Le succès de la physique tient à sa capacité à simplifier des phénomènes complexes jusqu’à les faire tenir en une petite équation. Par exemple, il est possible de modéliser l’attraction gravitationnelle entre deux corps en combinant les attractions individuelles de chacun des atomes constituants les corps et en ne considérant que le centre de masse résultant. Malheureusement, ce principe de compression de l’information ne s’applique pas pour tous les phénomènes, certains algorithmes sont incompressibles.)
Une suite de nombres est dite aléatoire si, pour l’engendrer, il n’existe pas d’autres moyens que de l’écrire complètement |
A contrario, si on peut compacter ce nombre par une technique quelconque, alors il n’est pas aléatoire |
- Martin-Löf donne une définition statistique du hasard
- Il a été démontré que les deux définitions sont équivalentes
- la définition de Chaitin – basée sur la complexité
- et celle de Martin-Löf – basée sur les statistiques
Ce nombre mystérieux est un nombre réel d’une complexité maximale, il est incompressible, c’est à dire qu’aucun programme ne peut en donner les N premières décimales en moins de N lignes de programme.
Autrement dit il est incalculable. Mais malgré tout il paraît «presque calculable», et Chaitin explique ses principales propriétés .
Les mathématiciens adoptent dans leur pratique des attitudes philosophiques variées, voire opposées.
Chaitin participe à un courant semi-empiriste,qui considère les mathématiques comme une discipline expérimentale au même titre que la physique,l’expérience se faisant sur ordinateur (Parmi eux : D. Bailey, J. Borwein, D. Zeilberger). L’argument principal de Chaitin à l’appui de cette thèse est le suivant :
Contrairement à l’opinion des mathématiciens «classiques»,le résultat d’incomplétude n’est pas un fait isolé, la plupart des énoncés mathématiques,en particulier les plus intéressants d’entre eux, sont inaccessibles à toute démonstration, il vaut mieux chercher à les vérifier expérimentalement ou heuristiquement.
Les revues mathématiques se sont ouvertes à cet état d’esprit. On cherche activement des méthodes informatiques de recherche d’énoncés intéressant,ou de démonstrations,ou de vérification de preuves.
Chaitin s’est appuyé sur la notion de programme informatique pour donner une définition mathématique rigoureuse de ce qu’est un «nombre aléatoire», un nombre (réel, avec une infinité de décimales) choisi au hasard. Il s’est inspiré pour cela d’idées introduites par Emile Borel au début du vingtième siècle.
On définit d’abord la complexité d’un nombre quelconque par l’intermédiaire de la longueur d’un programme informatique minimal le définissant. Un nombre aléatoire est un nombre tel que tout programme permettant de calculer les N premières décimales est de longueur sensiblement égale à N.
Chaitin a ainsi posé les fondements (indépendamment du célèbre mathématicien Andrei Kolmogorov), d’une nouvelle discipline,la théorie algorithmique de l’information.
Après un exposé historique tout à fait abordable de la célèbre «hypothèse du continu» posée au début du vingtième siècle, puis du résultat (1931) de Kurt Gödel sur l’incomplétude (selon lequel Il existe des faits mathématiques vrais mais indémontrables),qui a ruiné les espoirs de l’école axiomatique de David Hilbert, Chaitin explique simplement les travaux d’Alan Turing,inventeur de l’ordinateur –la machine de Turing – sur le problème de l’arrêt, en 1936 . Le problème de l’arrêt est le suivant : existe-t-il un programme universel permettant d’indiquer si un autre programme arbitrairement donné s’arrête au bout d’un nombre fini d’étapes?
La réponse donnée par Turing est négative.
Les propositions indécidables de Gödel ont eu de nombreux prolongements en informatique.Plus de 85 ans après sa découverte en 1930, le théorème d’incomplétude de Kurt Gödel (toute théorie formelle non contradictoire des mathématiques contient des propositions indécidables, c’est-à-dire dont on ne p o u r ra démontrer ni qu’elles sont justes ni qu’elles sont fausses) suscite encore des interrogations et fait l’objet de compléments.Très tôt, avant même la conception des premiers ordinateurs, A. Turing élabora la théorie des machines de Turing, qui introduisaient des concepts encore en vigueur actuellement : entrée, sortie, mémoire et programme.
|
Les nombres Ω de Chaitin.« Pour définir un nombre (réel), il est nécessaire et suffisant de donner toutes ses décimales »…
On ne peut pas calculer T en vertu du théorème de l’arrêt. On peut connaître une infinité de ses décimales (celles qui correspondent aux programmes dont on sait s’ils s’arrêtent ou non), mais une infinité d’autres resteront cachées. Cette présentation des nombres Ω est tirée d’un article paru sous la plume de J.-P. Delahaye dans la revue Pour la Science n° 295 (mai 2002), pp. 98-103, lisible ici. Notenote 1 cf. le problème de l’arrêt. |
There is definately a lot to find out about this issue. I like all the points you have made.|