From madore@clipper.ens.fr Mon Oct 30 18:37:03 2000
Article: 3294 of ens.forum.sciences.maths
Path: eleves!not-for-mail
From: madore@clipper.ens.fr (GroTeXdieck)
Newsgroups: ens.forum.sciences.maths,ens.forum.sciences.informatique
Subject: Re: Pour la Science
Supersedes: <8tkbjv$dn4$1@clipper.ens.fr>
Followup-To: ens.forum.sciences.maths
Date: Mon, 30 Oct 2000 17:37:03 +0000 (UTC)
Organization: Forum.
Lines: 90
Sender: madore@clipper.ens.fr
Message-ID: <8tkbvf$hjv$1@clipper.ens.fr>
References: <8tjpg5$bkh$1@clipper.ens.fr>
NNTP-Posting-Host: clipper.ens.fr
X-Trace: clipper.ens.fr 972927791 18047 129.199.129.1 (30 Oct 2000 17:43:11 GMT)
X-Complaints-To: forum@clipper.ens.fr
NNTP-Posting-Date: Mon, 30 Oct 2000 17:43:11 +0000 (UTC)
X-Newsreader: Flrn (0.4.0 - 07/99)
X-Start-Date: 30 Oct 2000 16:09:22 GMT
X-Mark: BOG
Xref: eleves ens.forum.sciences.maths:3294 ens.forum.sciences.informatique:284

Je peux raconter un peu ce que je sais (pour plus de précisions, voir
l'article « Kolmogorov Complexity and its Applications » de M. Li et
P. M. B. Vitányi dans le *Handbook of Theoretical Computer Science*,
volume A, et notamment la section 3.6).

Fixons une fois pour toutes une théorie mathématique sympathique
(i.e. récursivement axiomatisable et consistante), disons
l'arithmétique de Peano ou la théorie des ensembles de
Zermelo-Fraenkel.  Attribuons à chaque proposition P bien formée du
langage une probabilité[*] m(P) strictement positive, de sorte que la
probabilité totale (la somme des m(P) sur toutes les propositions)
soit 1.  Ceci implique notamment (critère de Cauchy) que la
probabilité m(P) tend vers 0 (dans n'importe quel sens du terme)
lorsque la longueur des propositions tend vers l'infini.

Considérons maintenant la probabilité Omega qu'une proposition
aléatoire (distribuée suivant les probabilités que nous avons
choisies) soit un théorème.  Autrement dit, Omega est la somme des
m(P) pour tous les P qui sont des théorèmes de la théorie.  C'est le
« nombre de la sagesse de Chaitin ».  Évidemment, Omega est
strictement compris entre 0 et 1, puisque certaines propositions sont
des théorèmes et que certaines n'en sont pas.

Supposons que je connaisse un encadrement Omega1<Omega<Omega2 de
Omega.  Lançons maintenant un programme qui va produire successivement
toutes les démonstrations de la théorie, de façon à énumérer un par un
tous les théorèmes.  À chaque théorème P listé, le programme ajoute (à
une variable qui initialement valait 0) la probabilité m(P) associée
(d'après l'hypothèse faite, voir la note [*], on peut bien faire ce
calcul).  La somme effectuée tend vers Omega en croissant, puisque
chaque théorème doit être énuméré tôt ou tard.  Elle (la somme) finira
donc forcément par dépasser Omega1.  Quand elle le fait, on sait alors
que toute proposition P telle que m(P) >= Omega2-Omega1 qui n'a pas
encore été énuméré par le programme ne *peut pas* être un théorème
(car s'il l'était, quand on l'énumérerait, la somme dépasserait
Omega2).  Donc connaître un encadrement Omega1<Omega<Omega2 nous
permet de connaître à coup sûr en temps fini la théorémitude ou
non-théorémitude de toute proposition P telle que m(P) >=
Omega2-Omega1.  Notamment, connaître les k premiers chiffres binaires
de Omega permet de connaître la théorémitude de toute proposition P
telle que m(P) > 2^-k.

Ensuite, il s'agit de bien choisir m pour avoir une conclusion
intéressante.  C'est la distribution de Solomonoff-Levin.  Je n'ai pas
vraiment envie de me casser la tête avec des questions de
self-délimitation des chaînes binaires, donc je vais faire grossier et
me contenter d'une constante multiplicative là où je pourrais obtenir
« presque » une constante additive.

Soit Ln l'ensemble de toutes les propositions de longueur n.  Son
cardinal ne dépasse pas A^n, où A est le nombre total de symboles du
langage.  J'affecte à chaque élément P de Ln une probabilité m(P)
égale à 2^-n divisé par le cardinal de Ln (autrement dit, la
probabilité totale de Ln est 2^-n ; enfin, bon, *proviso* le fait que
chaque Ln est non vide, mais on n'osera quand même pas me faire chier
à ce sujet).  Dans ce cas, on voit que dès lors qu'on connaît les k
premiers bits de Omega, on connaît au moins la théorémitude de toute
proposition de longueur inférieure à k/(lg(2A)), où le lg est un log
base 2.

Concrètement, ça veut dire que pour une certaine constante universelle
C (qu'on peut prendre égale à lg(2A) ; mais en fait n'importe quoi de
supérieur à lg(A) conviendrait déjà, et on peut même dire des choses
plus précises), il existe une fonction récursive (un programme ; une
machine de Turing ; ce qu'on voudra) qui, quand on lui fournit au
moins C·n bits d'information, est capable de dire si n'importe quelle
proposition de longueur (inférieure ou égale à) n est, ou non, un
théorème.  Et, bien sûr, de produire la démonstration qui convient.

C'est déjà un résultat impressionnant, car il affirme que les
démonstrations mathématiques, et même le fait de savoir si une
proposition est un théorème, se compriment très bien.  Précisément :
la complexité de Kolmogoroff de la liste de toutes les démonstrations
de tous les théorèmes de longueur inférieure ou égale à n est O(n),
c'est-à-dire peut se comprimer (asymptotiquement pour n grand) en O(n)
bits.

Maintenant, on peut prendre ça par contraposée.  Si un théorème a une
preuve très compliquée (au sens de la complexité de Kolmogoroff et pas
juste de la longueur), alors il est forcément très long.  Si on
accepte que tous les théorèmes utiles sont courts, alors il est
forcément très inutile.

Pas besoin de préciser que ceci est monstrueusement, mais vraiment
*monstrueusement* pipotesque.

[*] On fera les hypothèses que toutes ces probabilités sont
rationnelles, et que le rationnel m(P) en question se déduit de façon
récursive de P.  Ceci pour permettre d'ajouter les probabilités au fur
et à mesure qu'on énumère les théorèmes.