Gregory Chaitin : Hasard et complexité en mathématiques (I)

Cet ouvrage est une présentation vulgarisée d'une grande partie de l'oeuvre de l'auteur, dont la contribution majeure consiste en une définition mathématiquement correcte du hasard.

Il introduit le concept de complexité algorithmique = la longueur du  programme le plus court produisant une suite donnée. Dès lors, une suite de nombres est considérée comme aléatoire si sa complexité algorithmique est du même ordre que sa longueur.

Note : il est en général impossible de démontrer qu'un programme est  le plus court pour produire une suite donnée. La  complexité algorimithmique d'une suite n'est donc définie qu'à une constante additive près, et ne prend son sens que  lorsque la longueur de la suite tend vers l'infini.

Quel lien entre l'incalculabilité et  le hasard (le calcul par des programmes) ? Omega ? C'est le thème du livre.

Le travail de Chaitin souligne que l'incalculabilité est la norme. Les nombres calculables (ex : solution de l'équation x²-3=0 ) sont l'exception.

(note  :  pi ou sqrt(3) sont des exemples de réels calculables ; cf. Wikipedia. Que leur nombre de décimales soit infini n'est pas dérangeant ici : l'important est qu'il est possible de les calculer avec une précision arbitraire.)



1) Le premier chapitre met en lumière certains points d'histoire des mathématiques.


programme de David Hilbert : volonté de former un système axiomatique formel, valable pour l'ensemble des mathématiques. Ceci revient à définir un  langage dépourvu de la moindre ambiguité (avec son alphabet de symboles, sa grammaire, son système d'inférences, ainsi que son algorithme de contrôle ou procédure de décision, permettant de valider tout algorithme ou démonstration). Une conséquence d'un tel système est que le calcul ainsi mécanisé peut être confié à une machine. Emil Post remarquera d'ailleurs (post Turing) qu'il existe un algorithme capable de générer tous les théorèmes (l'idée théorique est de générer tous les théorèmes possibles, par ordre de taille de la démonstration
Gödel démontre l'existence de propositions indécidables dans tout système axiomatique formel qui contient l'arithmétique (ce système est donc dit incomplet). Dans tout système axiomisé, on débouchera toujours des propositions à la fois vraies et indémontrables. Et si l'on rajoute alors des axiomes au système pour trancher ces propositions problématiques, il restera encore d'autres propositions indémontrables !

   Le rêve caressé par Hilbert d'un SAF unique valable pour les mathématiques dans leur ensemble était un rêve impossible, car la totalité de la vérité mathématique ne peut être contenue dans un seul système formel. Les mathématiques n'ont rien de figé [...] Le système formel doit être régulièrement étendu par l'ajout de nouveaux principes, de nouveaux concepts, de nouveaux axiomes, comme c'est le cas en physique (et sans qu'il soit besoin de les démontrer, puisqu'ils fonctionnent !)

Turing a réduit la notion d'indécidabilité à celle d'incalculabilité, en démontrant l'impossibilité du problème de l'arrêt.

Démonstration par l'absurde : admettons l'existence d'un SAF permettant de déterminer, pour un programme, s'il s'arrêtera ou non. Il  nous est possible de générer tous les théorèmes du système ; donc, pour un programme particulier qui nous intéresse, d'obtenir la démonstration établissant son arrêt ou son non-arrêt.

Or ceci est impossible, car contredisant la thèse de Turing : il n'existe pas d'algorithme permettant de prédire si un programme donné s'arrêtera. L'incalculabilité est donc une cause profonde de l'incomplétude.



Ce premier chapitre, après avoir présenté 3 manières de démontrer l'infinité de l'ensemble des nombres premiers, est l'occasion pour l'auteur de déclarer sa flamme pour le langage informatique LISP, et de se livrer à de telles envolées lyriques :

   Si l'on en élimine les éléments "utiles", rajoutés pour en faire un outil "pratique", reste le LISP original, son coeur conceptuel, un joyau de splendeur mathématique et de beauté intellectuelle austère.

(ndjb : Ce mépris théoricien pour l'utilité ne peut que renvoyer aux propos d'un autre esthète, le maître Théophile Gautier, qui écrivait : "L'endroit le plus utile d'une maison, ce sont les latrines.")

Dans LISP, on parle pas de programmes, mais d'expressions. Ces expressions, on ne les lance ni ne les exécute, on les évalue, obtenant ainsi une valeur. Il n'y a pas d'effet secondaire. L'état de l'univers reste inchangé

Chaitin rapporte avoir vu la lumière à l'instant où il a programmé son premier interpréteur LISP, en Fortran. (TODO : en faire autant en Python)

   Comprendre équivaut à traduire en termes mathématiques[...]. On ne comprend que ce qu'on est capable de programmer, et de programmer soi-même.

Le premier chapitre offre en conclusion quelques réflexions de Chaitin,  sur son intuition de vivre dans un univers qui est ultimement discret (vs. continu) dans sa strucure.

Points importants :

•    compris dans quelle mesure un programme peut ne jamais se terminer : si on lui demande la solution d'une équation qui n'en comporte pas, le programme va chercher indéfiniment.

• L'indécidabilité n'est pas, pour les systèmes formels, une maladie rare : elle y est centrale.).

Critiques/Questions/débats :

•    le format du livre oblige l'auteur à se livrer à de gigantesques ellipses. Ceci est d'ailleurs un parti-pris, puisque Chaitin avoue que les grandes idées l'intéressent davantage que les démonstrations détaillées. Néanmoins, la compréhension s'en ressent parfois AMHA.

•    rien compris à la notion d'équation diophantienne universelle, qui permet de résoudre n'importe quel calcul.

• En introduction, un plaidoyer authentiquement émouvant et convaincant, montrant que les mathématiques sont loin d'être une science froide, mécanique et figée, où régnerait une "perfection statique", où les questions pourraient être tranchées une fois pour toutes :

Face au processus de découverte et de création, les mathématiciens sont comparables aux artistes : conduits par leur intuition et leur inspiration,ils obéissent à des motivations et des pulsions inconscientes ; ils se laissent guider par leur sens esthétique.

Pour qu'un concept perdure, il lui faut posséder beauté et fécondité.

Bibliographie :

Tobias Dantzig : Le Nombre

Stephen Wolfram : A New Kind of Science

Ernest Nagel : Le Théorème de Gödel