Et, si c’est l’incertain dès le départ !

L’incertain comme fondement, alors.

C’est cette idée folle qui germa chez Chaïtin.

Il se peut que le problème soit plus vaste et que Gödel et Turing sont juste le dessus de l’iceberg.

Il se peut que les choses soient pires et que ce que nous avons réellement là, en mathématique pure, ce soit l’aléatoire.

En d’autres mots , il se peut que parfois la raison pour laquelle on ne puisse pas prouver une chose, ce n’est pas parce qu’on est stupide ou que l’on ait pas assez travaillé assez longtemps dessus, il se peut donc que cette raison de ne pas trouver de preuves soit tout bonnement qu’il n’y a rien derrière !

Parfois la raison pour laquelle on ne peut pas trouver la solution à un problème n’est pas dûe au fait qu’on ne soit pas assez sympathique ou qu’on ne soit pas assez déterminé, c’est tout simplement parce qu’il n y a pas de solution ; soit que la question mathématique n’ait pas de structure soit que la réponse n’ait pas modèle soit qu’il n’y ait ni ordre ni structure disponibles dans le monde des mathématiques pures pour essayer faire naître la compréhension.

Donc, il se peut que, parfois, la raison pour laquelle on ne voit ni modèle ni structure c’est peut-être parce qu’il n’y a justement ni modèle ni structure !

De l’aléatoire dans les entiers ?

Une des illustrations que l’on peut en avoir est de regarder comment se distribuent les nombres premiers. Il semble qu’il y ait une certaine part d’aléatoire dans la distributions des entiers premiers. C’est un des chemins que certains n’hésitent pas à prendre pour essayer d’appréhender les entiers premiers. Et cette approche stochastique se fait en plein dans la théorie des nombres qui est, disons-le tout net, le cœur même des mathématiques pures.

D’un côté on n’hésite plus à user de probabilités pour tenter de comprendre les entiers premiers. Ce qui est une approche plutôt heuristique et peut-être même cognitive.

De l’autre côté on a « Dieu qui joue aux dés en physique fondamentale » ce qui exprime l’idée que ce qui se passe au niveau le plus bas de la matière est de nature aléatoire.

Comment, alors ne pas commencer à soupçonner que, peut-être, il en va de même dans les fondations même des mathématiques.

 

C’est en tous cas ce qu’a pensé Chaïtin.

Une première étape était de clarifier la notion d’aléatoire.

Mais qu’est-donc l’aléatoire ?

Qu’est-ce qu’on entend par absence de structure, absence d’ordre, absence de modèle ?

                        Aléatoire : absence de structure

C’est plus une sorte de notion de nature logique de l’aléatoire qu’une notion de nature statistique.

Ce n’est pas comme en physique où on peut dire qu’un processus est aléatoire comme le jet d’une pièce de monnaie. On ne se préoccupe pas d’où viennent les objets.

On examine quelque chose et on dit si cette chose possède une structure ou un modèle ou non.

Donc ceci est de nature logique ou structurellement aléatoire et s’oppose à la non-prédicabilité et l’aléatoire physique.

C’est différent.

C’est très lié, mais c’est différent.

Et l’idée qui vint avec - et Kolmogorov eut de façon indépendante en même temps la même idée- c’est l’idée que quelque chose est aléatoire quand on ne peut pas substituer à sa description, une autre description strictement plus petite. On parlera plutôt de compression au lieu de substitution et de concision au lieu de petitesse.

En d’autres mots une théorie n’est pas compressible lorsqu’il n’existe pas d’autre théorie plus concise qui la reproduise.

Par exemple, un ensemble de données physiques serait aléatoire si la seule façon d’exhiber l’ensemble de données était sous la forme d’une table, mais s’il existe une théorie, on peut compresser un grand nombre d’observations en un nombre petit de lois ou de principes physiques.

Et plus la compression est grande et meilleure est la théorie : en accord avec le principe d’Occam, la meilleure des théories est la plus simple des théories.

On peut soutenir, qu’en fait, un programme n’est rien d’autre qu’une théorie.

Si on se représente une théorie comme un programme qui calcule des observations. Plus le programme est petit, par rapport à la sortie qui constitue l’ensemble des observations, et meilleure est la théorie que représente ce programme.

C’est aussi ce que font les axiomes. Il y a là, la même idée dans les axiomes.

On a un grand nombre de théorèmes ou de vérités mathématiques et on arrive à les compresser sous la forme d’un système d’axiomes.

L’intérêt de cela est en fait l’économie du risque.

N’oublions pas que les axiomes sont des hypothèses qu’on doit faire et à chaque fois .

A chaque fois, qu’on fait une hypothèse on doit croire à cela et il s’introduit une part de risque.

On ne peut pas prouver à partir de rien du tout, on doit donc prendre l’axiome comme donnée. Dans un raisonnement, moins on introduit de supposition et plus sain il sera.

Donc moins on a d’axiomes et mieux c’est.

Donc, plus on aura de théorèmes compressés en un corps de théorie, et le mieux ce sera, et ceci aussi bien en mathématique qu’en physique.

On doit définir en premier la notion de manque de structure ou d’aléatoire. Si on trouve de l’aléatoire ou un manque de structure ou un manque de modèle en mathématiques pures, on doit d’abord dire ce que l’on entend par là.

 

Théorie algorithmique de l’information

Chaïtin appelle cela la théorie algorithmique de l’information. Cela concerne l’information algorithmique. On peut aussi dire complexité ou complexité en-taille-de-programme.

            Algorithmique Information

Le concept de base est de regarder la taille du programme le plus concis, le plus petit programme

-          on ne se préoccupe pas du temps d’exécution-

-          c’est le programme le plus concis qui calcule un objet. C’est le nombre de bits qu’on doit à un programme pour qu’il soit capable de produire cet objet. C’est la description algorithmique la plus concise d’un objet et c’est ainsi qu’on mesure sa complexité, le contenu de son information algorithmique ou sa complexité en terme de taille de programme.

C’est comme la théorie récursive des fonctions : on ne se préoccupe pas du temps d’exécution.

Alors que se passe-t-il donc quand on commence à regarder la taille des programmes ?

Un objet est aléatoire si le plus petit programme qui le calcule a la même taille que lui et il n’y a aucune compression possible.

Donc l’idée globale c’est de regarder la taille des programmes d’ordinateur, en ne tenant pas compte du temps d’exécution, même si ça demande un milliard d’année, l’information est la seule chose qui compte, le nombre de bits d’information, la taille des programmes.

Que se passe quand on commence à jouer avec cette idée ?

Ce qui se passe, en fait, c’est que partout où on se tourne on obtient l’incomplétude et l’indécidabilité, et on l’obtient de pire des manière possibles.

Par exemple, ceci arrive avec la première des choses qu’on veut faire : on ne peut jamais décider si une chaîne individuelle de digits satisfait cette définition de l’aléatoire.

Impossible ! On ne peut jamais calculer complexité en-taille-de-programme de quoi que ce soit.

On ne peut jamais déterminer quelle est la taille du plus petit programme.

Si on a un programme qui calcule quelque chose, qui donne une borne supérieure, sa taille est une borne supérieure de la complexité en taille de programme de ce qu’il calcule. Mais on ne peut jamais prouver aucune borne inférieure.

Et c’est le premier résultat d’incomplétude de Chaïtin.

En théorie normale de la complexité celle où on tient plus compte du temps que des bits d’information, les bornes inférieures sont beaucoup plus difficile que les bornes supérieures. Obtenir une borne inférieure est beaucoup plus difficile que d’obtenir une borne supérieure. Parce quand on trouve un algorithme plus astucieux on a en même temps une borne supérieure du temps qu’il faut pour calculer quelque chose ; si on trouve une méthode qui soit rapide on a, en fait, montré en même temps aussi que cela peut se faire avec cette rapidité.

Le vrai problème est de montrer que l’on a l’algorithme le plus rapide possible.

Ce qui est plus difficile.

Mais cela peut être fait dans certain cas, pour une classe d’algorithmes possibles.

Maintenant, en Information Algorithmique (on ne tient plus compte du temps) ce n’est plus du tout possible et on peut prouver aucune borne inférieure.

L’idée de base est qu’on ne peut prouver aucune borne inférieure en terme de complexité en-taille-de-programme d’objets individuels. Donc en particulier même si la plupart des chaînes de digits satisfont à cette définition de l’aléatoire, ils sont incompressible dans ce sens, ils sont aléatoires dans le sens de l’absence de structure caractéristique.

On peut s’apercevoir très facilement que la plupart des objets qui satisfont cette définition n’ont pas de structure. Si on regarde toutes ces centaines de nombres digitaux, presque tous n’ont pas de structure selon cette définition, mais on ne peut jamais en être sûr dans des cas individuels.

On ne peut pas prouver l’absence de structure dans les cas individuels .

Plus précisément, il peut y avoir finitairement plusieurs exceptions.

Avec N bits d’axiome on peut déterminer tous les objets dont la complexité en taille de programme est au plus N. Mais c’est le plus loin où on peut aller.

Un nombre encore plus complexe que le plus complexe des nombres transcendants connus: Omega 

Le pire résultat de Chaïtin sur l’incomplétude quand on a affaire à une absence totale de structure en mathématiques pures nécessite l’introduction d’un nombre qu’il appelle la probabilité d’arrêt.

 = probabilité d’arrêt

Considérons le réel  qui est la probabilité qu’un programme tiré  au hasard s’arrête. C’est une moyennisation du problème de l’arrêt d’une machine de Turing. Et ,pourvu que le langage de programmation soit spécifié ceci donne un nombre réel bien déterminé.

_machine = probabilité d’arrêt.

Donc dés qu’on le décide  est un nombre réel et bien défini. Mathématiquement, ce n’est pas un objet très sophistiqué. Cependant il ressort de cet objet  qu’il est maximalement inconnaissable !

 est maximalement inconnaissable 

Que veut dire exactement l’expression maximalement inconnaissable.

Cela concerne les bits ou les digits de ce nombre.

Une fois fixé le langage de programmation de la machine cette probabilité d’arrêt , nous l’avons dit, est un nombre réel bien spécifique, qui dépend du choix de la machine ou du langage de programmation dans lequel on génère au hasard un programme.

Ce nombre spécifique, écrivons-le en binaire, et donc on obtient une séquence de 0 te de 1.

Il s’avère que ces 0 et ces 1 ne font apparaître aucune structure.

Ils ne peuvent pas être compressés.

Pour calculer les N premiers bits de ce nombre binaire cela exige un programme de N bits.

Pour prouver ce que sont ces N premiers bits de ce nombre ceci exige N bits d’axiomes.

C’est une information mathématique irréductible.

 est une information irréductible

 

Une information mathématique irréductible ?

Voilà une idée qui ne manque pas d’être absolument choquante parce qu’une idée normale en mathématique, une de ces bonnes idées à la Hilbert, doit être telle que toute vérité mathématique peut être réduite à un petit ensemble d’axiomes qu’on peut accepter et qui seraient, si possible, self-évidents.

Mais si on veut déterminer quels sont les bits de la probabilité d’arrêt  , ceci ne peut pas être réduit par quelque chose d’autre qui soit plus simple.

 possède une définition mathématique avec une structure plutôt simple dès qu’on spécifie l’ordinateur ou le langage de programmation et Chaïtin a même écrit un programme en LISP qui calcule ce nombre au sens faible.

Bien que  soit maximalement inconnaissable on peut toujours essayer de l’obtenir comme limite à partir la formule ci-dessous

 =  _{p s’arrête} 2 ^-p

 

Mais cela converge très, très très, très, lentement –on ne peut jamais savoir de combien on est proche du nombre à calculer

—il n’existe pas de régulateur calculable de la convergence et il n’y a pas moyen de décider de ce qu’il reste à faire pour obtenir les N premiers bits de .

Pour obtenir  à la limite à partir de la formule ci-dessous, on doit considérer de plus en plus de programmes de plus en plus longtemps et à chaque fois qu’on voit un programme s’arrêter, ceci contribue de 1/2^k à la probabilité d’arrêt.

 =  _{p s’arrête} 2 ^-p

Donc le temps qu’il faut pour obtenir les N premiers bits de  croît comme le temps d’exécution fini, le plus long, d’un programme de N bit.

De manière plus précise on peut dire que chaque programme qui permet de définir  doit être généré aléatoirement comme par le jet d’une pièce de monnaie pour chacun de ses bits. Le point crucial est que le programme doit être auto-délimité. L’ordinateur doit obtenir le programme bit après bit. Chaque fois que l’ordinateur demande un bit du programme, on jette la pièce à pile ou face. Et l’ordinateur doit décider de lui-même s’il a suffisamment de bits c’est à dire s’il a le programme entier. Le programme doit être auto-délimité pour définir cette mesure de probabilité correctement. Il n’y a pas de blanc pour indiquer la fin d’un programme : un programme doit indiquer en lui-même l’information de sa propre longueur à l’aide d’une certaine astuce, d’une certaine astuce codée. C’est le seul aspect technique pour obtenir que cette probabilité soit bien définie.

C’est aussi le point technique de la théorie de Chaïtin.

 est donc un nombre compris entre 0 et 1. C’est la probabilité qu’un programme dont les bits ont été générés aléatoirement par les jets indépendants d’une pièce de monnaie non-faussée, s’arrête.

Pour fixer les idées, le langage de programmation choisi par Chaïtin est LISP et la machine est une machine de Turing.

Donc  est maximalement inconnaissable. C’est un cas où la vérité mathématique n’a ni structure ni modèle et c’est quelque chose que nous n’aurons jamais.

Ce qui a été obtenu là est de l’aléatoire au maximum.

n  C’est analogue aux jets indépendants d’une pièce de monnaie en mathématiques pures.

  En fait, Chaïtin peut aussi le faire, à la manière de Gödel, dans la théorie élémentaire des nombres. Chaïtin a construit la détermination des bits de  à partir d’une équation diophantienne.

Suite de l'article

---