Voici une question un peu provocante : qu'est-ce qu'un nombre aléatoire ? Pour un probabiliste, elle n'a pas de sens : un nombre n'est pas aléatoire (le nombre π, par exemple, ça n'a pas de sens de dire qu'il est aléatoire), ce qui a un sens, c'est de tirer aléatoirement un nombre, disons, dans l'intervalle [0;1]. Pourtant, il y a des branches des mathématiques où cela a bien un sens, de façon absolue, de dire qu'un nombre réel bien défini est — ou n'est pas — aléatoire (et, pour gâcher le suspens, le nombre π n'est pas aléatoire, en aucun sens qu'on sache définir à ma connaissance, ce qui est bien dommage parce que ça permettrait de prouver plein de choses merveilleuses à son sujet, mais c'est tout à fait intuitif parce qu'on arrive à le calculer — donc il n'est certainement pas tiré au hasard !). Je vais tâcher d'expliquer simplement de quoi il retourne, sans entrer dans trop de technicité mais en donnant tout de même des définitions complètes. L'idée qu'on cherche à développer est que :
L'aléatoire est ce qu'on ne peut prévoir (de façon non triviale) par le calcul.
Plutôt que de travailler sur des nombres réels, je travaillerai sur
des suites infinies de 0 et de 1, ce qui est presque pareil (comme
aucun rationnel dyadique, ou aucun rationnel tout court, d'ailleurs,
n'est aléatoire en aucun sens, on peut considérer qu'une suite infinie
de 0 et de 1 est la même chose que le nombre réel entre 0 et 1 qui a
cette écriture binaire). Appelons Ξ (j'allais l'appeler 𝔠,
mais je pense que si je fais ça beaucoup de gens ne vont rien voir
d'utile) l'ensemble des suites infinies de 0 et de 1. On aura besoin
de la notion d'ouvert de Ξ: un ensemble U de
suites est dit ouvert lorsque c'est une réunion d'ensembles de la
forme toutes les suites commençant par <un nombre fini de
symboles>
; ou, de façon équivalente, lorsque pour toute suite
de U il existe un rang à partir duquel on peut modifier
n'importe comment la suite et rester dans U. Autrement
dit, l'ensemble de toutes les suites commençant par 0, ou par
01101001, ou par 11111111, sont des ouverts, ainsi que n'importe
quelle réunion — même infinie — de telles choses (par
exemple, l'ensemble des suites commençant par 0 ou
11 ou 100 ou 1011 ou…), et ce sont
là tous les ouverts de Ξ. (La notion d'ouvert de Ξ ne coïncide
pas avec la notion plus habituelle d'ouvert de [0;1], par exemple
parce que Ξ n'est pas connexe, mais la différence n'est pas
importante pour ce que je vais dire.)
On dira qu'un ouvert (ou, d'ailleurs, n'importe quel ensemble) est dense lorsque son complémentaire (i.e., l'ensemble des suites qui ne sont pas dedans) ne contient aucun ouvert autre que ∅ (le vide, qui est un ouvert). Voici un exemple d'ouvert dense : l'ensemble de toutes les suites sauf la suite 000000… (ou sauf n'importe quelle suite donnée, d'ailleurs) : il est facile de vérifier que c'est un ouvert (c'est l'ensemble des suites commençant par 1, ou par 01, ou par 001, ou par 0001, autc.), et il est encore plus facile de se convaincre que son complémentaire (qui ne contient qu'une seule suite, la suite nulle) ne contient aucun ouvert non vide. L'idée est qu'un ouvert dense contient « quasiment toutes » les suites ; mais ça, ça va servir à définir les suites génériques, qui ne sont pas pareilles que les suites aléatoires.
Pour définir ce que c'est qu'une suite aléatoire j'ai besoin d'une
autre notion, celle de mesure d'un ouvert (moralement, la
probabilité qu'une suite de 0 et de 1 tirés au hasard indépendamment
avec probabilité ½ pour chacun, tombe dans l'ouvert). J'ai dit qu'un
ouvert pouvait s'écrire comme une réunion de machins qui
sont toutes les suites commençant par <bla bla
bla>
, où <bla bla bla> ne comporte qu'un
nombre fini de 0 et de 1 (on appelle de tels machins des ouverts
élémentaires) : avec un petit peu d'efforts on peut s'arranger
pour que la réunion soit disjointe (il suffit de retirer ce qui est
redondant dans la description : l'ensemble des suites commençant par 0
ou 01, c'est juste l'ensemble des suites commençant par 0). On
attribue à chacun de ces ouverts élémentaires une mesure qui est
½n (un demi puissance n) avec n le
nombre de symboles imposés au début, et on ajoute toutes ces mesures
pour calculer la mesure de la réunion disjointe. Par exemple,
l'ouvert des suites commençant soit par 0 soit par 111, a pour mesure
5/8 (= 1/2 + 1/8) ; l'ensemble des suites autres que la suite
000000… (j'ai expliqué plus haut que c'était un ouvert) a pour
mesure 1, comme l'ensemble Ξ de toutes les suites : un tel
ouvert est dit de mesure pleine. Il s'avère qu'un ouvert de
mesure pleine est forcément dense (pourquoi ?), mais la réciproque
n'est pas vraie — si ça ne vous saute pas aux yeux, c'est sans
doute normal, mais ça vaut le coup d'y réfléchir.
J'en viens à la notion de suite aléatoire et de suite générique.
Mais avant ça j'aurai besoin d'une notion de calculabilité ; pourtant,
je ne vais pas définir ce que c'est : ce qui est intéressant,
c'est que pour chaque notion de calculabilité
, je vais avoir
une notion de suite aléatoire et de suite générique, qui sera d'autant
plus contraignante que la notion de calculabilité est puissante. La
notion la plus naturelle, c'est la calculabilité habituelle de
Church-Turing
(les fonctions
récursives, qui sont en gros celles que peut calculer un
ordinateur idéalisé), mais plein d'autres notions pourraient
convenir : soit plus fortes (fonctions récursives sous un oracle
quelconque, fonctions Σn de
l'arithmétique, fonctions arithmétiques, fonctions hyperarithmétiques,
fonctions analytiques-au-sens-de-la-calculabilité, fonctions
constructibles-au-sens-de-l'univers-de-Gödel), soit plus faibles
(fonctions primitives récursives, et sans doute même fonctions
calculables en temps polynomial même si quand la calculabilité devient
trop faible j'ai peur que les notions que je vais définir ne soient
plus très bonnes).
Le but de ces fonctions calculables sera juste de pouvoir dire que
certains ouverts de Ξ sont calculables : un ouvert
calculable U sera juste un ouvert tel qu'une fonction
calculable (donc un programme informatique idéalisé, si vous prenez la
calculabilité au sens de Church-Turing) qui quand on lui présente un
mot fini de 0 et de 1 décide si l'ouvert élémentaire des suites
commençant par ce préfixe sera mis dans la réunion
constituant U. Autrement dit, on lui demande veux-tu
mettre dans l'ouvert toutes les suites commençant par
0 ?
, veux-tu mettre dans l'ouvert toutes les suites commençant
par 1 ?
, veux-tu mettre dans l'ouvert toutes les suites
commençant par 00 ?
, etc., et elle prend à chaque fois une
décision[#]. À titre d'exemple,
tant que votre notion de calculabilité n'est pas démesurément faible,
l'ensemble des suites qui ne sont pas la suite nulle — ensemble
dont j'ai déjà dit que c'était un ouvert par ailleurs dense et de
mesure pleine — est calculable, puisque c'est très facile de
reconnaître les mots 1
, 01
, 001
et de
répondre oui
sur chacun d'entre eux. On peut aussi demander
qu'une suite d'ouverts soit calculable : cela signifie que la
fonction calculable prend en outre en entrée un entier (n)
qui est le rang dans la suite. On définit enfin une suite
décroissante calculable d'ouverts de Ξ : cela signifie
simplement que la suite est décroissante pour l'inclusion (i.e.,
chaque ouvert est inclus dans tous les précédents), ou, si on préfère,
quand la fonction calculable a décidé d'exclure un ouvert élémentaire
d'un terme de la suite, elle exclut automatiquement de tous les
suivants.
Quel est maintenant l'esprit de la définition ? Une suite
aléatoire/générique est, en gros, une suite sur laquelle on ne puisse
pas faire une prévision calculatoire non-triviale. Évidemment, on
pourra toujours dire elle commence par 010100
(disons), puisque
c'est une suite bien définie (je rappelle que je suis en train de
définir une notion d'aléatoire qui s'applique pour une suite bien
définie !) ; mais l'idée est qu'on ne peut pas faire une
prévision vraiment intéressante.
Voici enfin les deux notions en question :
Une suite est dite générique lorsqu'elle appartient à tout ouvert dense calculable.
Une suite x est dite aléatoire lorsque pour toute suite décroissante calculable (Un) d'ouverts de Ξ telle que le n-ième soit de mesure au plus 1/n, la suite x n'appartient qu'à un nombre fini d'entre eux.
La définition d'une suite générique est sans doute plus simple à
comprendre : si vous arrivez à faire une prévision calculable du
type la suite n'est pas dans l'ouvert U que voici
,
alors cet ouvert ne peut pas être dense, c'est-à-dire qu'il y
a quelque part un gros bout (toutes les suites commençant par un
certain préfixe) qu'on a omis dans la prévision — qui n'a donc
rien de remarquable (je peux bien faire la prévision la suite
commence par 0101010
, et il y a bien certaines suites aléatoires
qui vont y coller). Dit autrement, un ouvert dense calculable
contient toutes les suites génériques. Donc j'ai déjà prouvé
que la suite 000000… n'est pas générique : il existe un ouvert
dense (toutes les suites sauf elle !) qui est calculable et
qui ne la contient pas.
La définition d'une suite aléatoire est un chouïa plus compliquée,
parce que cette fois-ci on demande de faire des prévisions du
type la suite est dans l'ouvert U que
voici
; or on peut certainement faire des prévisions de ce style
(de nouveau, je peux faire la prévision la suite commence par
0101010
, et il y a bien certaines suites aléatoires qui vont y
coller), on peut même certainement faire des prévisions aussi bonnes
qu'on veut, mais le point important est qu'on ne peut pas le faire
uniformément : si on a une suite décroissante calculable
d'ouverts dont le n-ième a une mesure au plus
1/n[#2], son
intersection ne contient aucune suite aléatoire. Ceci étant, on se
convainc facilement que, par exemple, la suite nulle 000000…
n'est pas aléatoire (de nouveau, dès que la notion de calculabilité
n'est pas démesurément faible) : il suffit de considérer la suite
décroissante d'ouverts donnée par les suites dont les n
premiers termes sont nuls — cela donne une mesure de
1/2n.
J'ai donc prouvé que la suite nulle n'était ni aléatoire ni
générique. C'est la moindre des choses. En fait, pour la même
raison, n'importe quelle suite calculable au sens qu'on s'est fixé
n'est ni aléatoire ni générique. En revanche, si je prends une suite
aléatoire (resp. générique) et que je remplace un sur deux de ses
chiffres par un 0, j'obtiens une suite qui n'est plus
aléatoire (resp. générique) et qui n'est pourtant pas calculable :
donc aléatoire
et génériques
ne sont pas synonymes
de pas calculables
— ils sont bien plus forts que ça.
Le fait qu'il existe des suites aléatoires et des suites
génériques résulte, si la notion de calculabilité est dénombrable
(i.e., s'il n'existe qu'une infinité dénombrable de fonctions
calculables ℕ→ℕ, ce qui est le cas pour la
calculabilité au sens de Church-Turing), résulte du théorème de Baire
dans un cas (l'intersection de tous les ouverts denses
calculables est non vide) et de l'additivité de la mesure dans l'autre
(la réunion de toutes les intersections de suites
décroissantes calculables d'ouverts dont la mesure tend vers zéro est
de mesure nulle). Pour d'autres notions, cela peut être plus
difficile ou impossible (si on déclare que toutes les fonctions
ℕ→ℕ sont calculables, il n'y a plus aucun nombre
aléatoire ou générique : pour un être omniscient, il n'y a pas de
hasard
).
Voici maintenant un résultat que j'ai toujours trouvé remarquable :
on s'imagine que générique
et aléatoire
veulent tous les
deux dire, de manière vague qu'on ne peut pas calculer de prévision
aléatoire non triviale dessus ; pourtant, pour toute notion (un tant
soit peu raisonnable) de calculabilité,
Aucune suite n'est simultanément générique et aléatoire.
La démonstration n'est pas compliquée ! Considérons, pour chaque n, l'ouvert Un de Ξ ainsi défini : il s'agit de l'ensemble des suites de 0 et de 1 qui commencent par k signes quelconques (pour un certain k fini) qui sont immédiatement suivis de 2k+n fois 0 (et ensuite n'importe quoi) : cette description montre immédiatement qu'il s'agit d'un ouvert, il est assez clair qu'il est calculable (il est très facile de reconnaître les mots formés de k signes quelconques puis 2k+n fois 0), et même, que la suite (Un) d'ouverts de Ξ est décroissante calculable. Maintenant, chacun des ouverts Un est dense (car vous aurez beau prescrire comme vous voudrez les N premiers termes d'une suite, vous n'éviterez jamais à qu'elle puisse être dans Un), et pourtant sa mesure est majorée par 1/2n ou quelque chose de ce goût-là (c'est une réponse à la question que j'avais posée plus haut : montrer qu'il existe des ouverts denses qui ne sont pas de mesure pleine). Du coup, une suite générique doit appartenir à chacun des Un, alors qu'une suite aléatoire ne peut appartenir qu'à un nombre fini d'entre eux. Cela empêche qu'une suite aléatoire soit générique.
Ce résultat est difficile à comprendre intuitivement : je pense que
les suites génériques sont plus élusives que les suites aléatoires
— elles donnent l'impression d'avoir des motifs dedans, ce qui
est faux, bien sûr, mais elles ne se comportent pas du tout comme les
suites aléatoires. Philosophiquement parlant, la suite de 0 et de 1
qu'on obtiendrait en tirant infiniment à pile ou face est
assurément aléatoire
, mais je ne sais pas d'où on pourrait
sortir une suite générique : notre monde a l'air beaucoup plus
naturellement orienté vers l'aléatoire que vers le
générique[#3] — pourtant,
mathématiquement, il existe une grande similarité entre ces deux
notions (voir à ce sujet
le livre
d'Oxtoby fort justement intitulé Measure and
Category).
Les suites (ou nombres réels) aléatoires et surtout génériques ont
une grande importance en théorie des ensembles : par exemple, la façon
dont Paul
Cohen a montré l'indémontrabilité de
l'hypothèse
du continu c'est de fabriquer
(par la technique
du forcing) énormément de suites de 0 et de 1 (ou
nombres réels) qui soient génériques (en fait, aléatoire marcherait
aussi) en prenant pour notion de calculabilité la constructibilité au
sens
de l'univers
de Gödel, qui est à peu près la plus forte qu'on puisse imaginer
(très très grossièrement, c'est la puissance qu'aurait en quelque
sorte un ordinateur capable de calculer directement sur les ensembles
et sur des temps transfinis). À l'autre bout du spectre de la
calculabilité, on pourrait placer la cryptographie, où la notion
d'oracle
aléatoire sert de modèle pour des preuves de sécurité de
cryptosystèmes et où on
est bien forcé de constater que ce n'est pas une notion si
atteignable. Je me demande s'il y aurait lieu de considérer des
oracles génériques (le terme a été utilisé, mais je crois que c'est
pour quelque chose se très différent).
[#] Pour la calculabilité au sens de Church-Turing, on peut prendre l'absence de réponse, i.e., la non-terminaison du programme, comme une réponse négative, ou bien l'interdire, ça ne changera rien à la notion d'ouvert calculable.
[#2] Ça fait partie des
choix pas forcément évidents à faire quand on prend une notion de
calculabilité trop faible… déjà, pour la calculabilité au sens
de Church-Turing, il faut se convaincre que le bon choix est bien
d'imposer explicitement une vitesse de convergence et pas juste de
dire la mesure de Un tend vers
0
: un des critères qui me poussent à faire ce choix, c'est que,
si je ne me trompe pas, il permet alors avec l'oracle de l'arrêt des
machines de Turing de construire un réel aléatoire (de même qu'on peut
en construire un générique), ce qui ne serait pas possible si on
demandait juste que la mesure tende vers zéro. Mais je ne suis pas
totalement sûr de moi, et je le suis encore moins pour des notions de
calculabilité très faibles comme la calculabilité en temps polynomial
(où ça fait une différence de demander que la mesure soit bornée par
1/n ou 1/2n), et même pour la
calculabilité de Church-Turing il faudrait calibrer les choses par
rapport à une autre définition habituelle (mais à mon avis moins
agréable) qui fait intervenir
la complexité
de Kolmogorov. Enfin bon, l'esprit est quand même raisonnable
dans tous les cas, et pour les notions de calculabilité assez fortes
(du genre être arithmétique
), ça ne fait pas de différence.
[#3] Voici un autre fait digne d'intérêt : un nombre réel générique est un nombre de Liouville, c'est-à-dire qu'il s'approche très bien par les nombres rationnels, alors qu'un nombre réel aléatoire est approché par les rationnels exactement à l'ordre 2 (c'est-à-dire qu'il est à une distance d'un rationnel de l'ordre de la puissance −2 du dénominateur de celui-ci) ; or il se trouve que les nombres qui interviennent « naturellement » en analyse, en tout cas le nombre e, sont ou ont l'air d'être, approchés exactement à l'ordre 2. Du coup, en un sens qui semble malheureusement impossible à rendre précis, les décimales de e ou π sont plus proches d'être aléatoires que génériques (en vérité, elles ne sont ni l'un ni l'autre : il faudrait une notion furieusement faible de calculabilité pour que π soit aléatoire !).