Auteur: Serge Boisse
Date: Le 27/03/2023 à 10:03
Type: web/MOC
Tags: maths,nombres,probabilité,complexité,Kolmogorov
pub: oui
commentaires: ouiCopier

Les nombres anti-aléatoires

Je vous invite à découvrir dans cette page les intéressantes propriétés d'une classe de nombres entiers que j'ai découverte, les "nombres anti aléatoires", ou "nombres singuliers".

Comme leur nom l'indique, il s'agit en quelque sorte de l'inverse de la notion de nombre aléatoire. Ces nombres anti-aléatoires sont des nombres très spéciaux, ceux dont la description est extraordinairement courte par rapport  leur taille.

Mais avant de parler des nombres anti-aléatoires, jetons un oeil sur ce qu'est, précisément, un nombre aléatoire.

Nombres aléatoires

Intuitivement, un nombre aléatoire est un nombre dont les chiffres semblent tirés au hasard. Par exemple 4951705567132089165  semble bien plus aléatoire que 12345678901234567890, ou que 3141592653589793.  Ce dernier nombre est simplement "pi  multiplié par  dix mille milliards".

Comment formaliser précisément cette intuition ? Pour cela, nous aurons besoin d'une fonction appelée "complexité de Kolmogorov", ou $K(n)$.

Un problème se pose aussitôt, car évidemment $K(n)$ dépend du langage informatique qu'on choisira pour coder le programme qui imprimera n. Mais il s'avère que c'est un faux problème car on peut démontrer mathématiquement que, pour de très grand nombres n,  si  $K_1(n)$  est la taille du plus court programme (qui imprime n) dans le langage 1, et $K_2(n)$  est la taille du plus court programme (qui imprime n) dans le langage 2,  alors le rapport $K_1(n)/K_2(n)$ restera compris entre des limites bornées (et généralement petites) qui dépendent uniquement des deux langages choisis.

Cela se comprend intuitivement : si pour décrire un très grand nombre n,  disons en français, ma description prend m mots, il est probable que la description de ce même nombre en anglais prendra un nombre de mots voisins de m.

Décrire, c'est expliquer algorithmiquement comment on peut calculer le nombre n de la manière la plus simple possible, et si le plus court algorithme est très long (ou très court) en français, alors cet algorithme sera également très long (ou très court) en anglais, ou en allemand, ou en japonais, ou dans un langage informatique comme C ou java (donc aussi sans doute en *javanaiscript 😊)

Les nombres aléatoires n'ont, intuitivement, aucune caractéristique qui permettrait de les décrire simplement.  Il n'y pas de moyen de les imprimer qui soient sensiblement plus courts que d'écrire l'instruction "print" suivie de ce nombre en base 10 (ou en base 2, ou dans une base quelconque, ce qui revient au même à une constante près)

On comprend donc la définition suivante :

Il faut comprendre que lorsque nous parlons de très grands nombres,  nous parlons ici de nombres comportant des millions de chiffres, voire plus. Si le plus court programme qui décrit  (au sens précédent) un nombre de dix millions de chiffres  possède plus de quelques millions de caractères,  alors ce nombre est, par définition, aléatoire. Inversement, si la description de ce très grand nombre ne prend que quelques milliers de caractères (ou moins), on peut être sûr que ce nombre n'est pas aléatoire.

Par exemple le nombre formé des dix millions de premières décimales de pi  peut être décrit par un programme de quelques centaines de caractères seulement, car il est assez facile de calculer les décimales successives de pi. Donc pi n'est pas aléatoire, et on s'en doutait un peu.

Ce qui est amusant, c'est que l'on peut prouver que presque tous les très grands nombres sont aléatoires ! En effet les nombres qui ont une description courtes sont rares.  Plus précisément,  si nous posons qu'un nombre n est aléatoire si le plus court programme qui le calcule est plus long que log(n)/100, alors parmi les 10 puissance 10000 nombres de dix mille chiffres, seuls quelques millions ne seront pas aléatoires car il n'y a que quelques millions de programmes (correctement écrits, imprimant un unique nombre n, et de plus les plus courts possibles) de moins de 100 caractères.

La complexité de Kolmogorov

Revenons à la fonction $K(n)$ qui est, rappelons-le, la taille du plus court programme qui calcule et imprime le nombre n. Il se trouve que K(n) est une fonction non-calculable.

Ceci veut dire qu'il n'existe aucun programme prenant n en argument et imprimant $K(n)$ pour tout n. Ce résultat signifie que nous ne saurons jamais trouver un algorithme qui pour un nombre entier n détermine le nombre minimal de bits ou d'octets du programme le plus court qui imprime n, ou encore que nous ne saurons jamais trouver une méthode qui nous permette de décrire de manière la plus concise possible n'importe quel entier n. L'ensemble des entiers naturels "échappe" ainsi à la calculabilité. Démonstration précise.

Ceci est toutefois moins surprenant qu'il n'y parait si on n'y réfléchit un peu : La fonction $K(n)$ est une fonction de "compression" qui retourne la description la plus courte (en terme de programme d'ordinateur) que l'on peut faire du nombre n. Cette fonction possède une énorme importance théorique, en particulier les nombres n tels que $K(n)\sim$ nombre de bits de n sont les nombres incompressibles ou aléatoires. Tous les nombres ne sont pas aléatoires, mais la majorité des nombres l'est, bien qu'il soit impossible d'en exhiber un !

De plus, si vous réfléchissez un peu, vous verrez que la fonction K doit être très astucieuse pour réussir à trouver le programme le plus court qui retourne un n donné ; Parfois, il faudrait même que K fasse usage de mathématiques vraiment très futées pour "penser à une idée qui permette de faire encore plus court". Le fait que K ne soit pas calculable nous dit simplement que K doit être plus futée que n'importe quel programme d'ordinateur ! En fait, je pense que l'aptitude à la compression de donnée" est une mesure de l'intelligence. Pour compresser une donnée, par exemple un nombre, nous devons trouver des régularités, des similitudes internes ou externes qui ne sont pas forcément visibles ; nous devons être très intelligents ; K étant la fonction de compression ultime par définition, c'est la fonction qui contient le plus d'intelligence de l'univers ; il n'est pas étonnant qu'elle ne soit pas calculable !

Curieusement, bien qu'on ne puisse pas la calculer, on peut majorer et minorer K(n) par des fonctions calculables :

Majoration

La plus simple des fonctions qui retourne un nombre (n) est simplement la fonction "return n;" dont la taille est 8 octets plus le nombre de chiffres de n, ou encore $8+{\log }_{10}n$. Par conséquent :

$$K(n)\le 8+{\log }_{10}n$$

D'autre part il existe des nombres incompressibles ou aléatoires (ce sont même la majorité des nombres) ; pour ces nombres, $$K(n)\sim 8+{\log }_{10}n$$ La fonction K s'approche donc parfois très près de notre majoration.

(notons que le choix du langage de programmation est arbitraire : nous avons choisi java, mais on arriverait a des résultats semblables avec une simple machine de Turing).

Minoration

K(n) peut prendre des valeurs arbitrairement élevées (Voir Lemme 1)

Définition : fonction tau(n) : $\tau (n)$

Considérons la fonction $n\to \tau (n)=\underset{i=n}{\overset{\mathrm{\infty }}{min}}K(i)$.

$\tau$ est la fonction qui relie "par en dessous" les minimum successifs de la fonction $K$. En particulier $\tau (n)=min(K(n),\tau (n+1))$

Pour tout n, $K(n)\ge \tau (n)$ ; en effet $\tau (n)=min(K(n),\tau (n+1))\le K(n)$.

$\text{Tau}$ est donc un minorant de $K$. C'est de plus un "bon" minorant : en effet quel que soit n, $tau(n+1)=\underset{i>n}{min}K(i)$, donc on peut trouver $i>n$ tel que $\tau (i)=K(i)$ ; K "touche" tau un nombre infini de fois.

Enfin, tau est une fonction croissante : $\tau (n)=min(K(n),\tau (n+1))\le \tau (n+1)$, et
$\underset{n\to +\mathrm{\infty }}{lim}\tau (n)=+\mathrm{\infty }$.

Nous avons donc un minorant de K qui est une fonction croissante, non bornée, qui atteint K un nombre infini de fois. 

Nombre anti-aléatoires

Une chose qui a son importance est que $\tau (n)$ croît extrêmement lentement. En effet on peut majorer tau par des fonctions calculables à croissance arbitrairement lente.

Considérons par exemple la fonction suivante, en apparence anodine, codée ci-dessous en langage java :

  static int ack(int p, int q) {  
    if (p==0) return q+1;  
    if (q==0) return ack(p-1,1)  
    return ack(p-1,ack(p,q-1));  
  }  
  static int retourne_n() {return ack(9,9);}
Copier

Cette fonction (en fait un couple de fonctions, mais n'ergotons pas), qui n'a l'air de rien, produit un nombre absolument monstrueux, inimaginablement grand : c'est la fonction d'Ackermann. Cette fonction est calculable et croissante, et même très rapidement croissante.

Pour donner une idée du nombre que renvoie la fonction retourne_n() , c'est à dire N = ack(9, 9) (n'essayez pas de la calculer avec votre ordinateur !) , il faut se livrer à quelques acrobaties mentales : imaginez que vous disposiez d'une feuille de papier de la taille de l'univers, et que vous pouviez y écrire à l'aide de caractères gros comme des atomes ; alors le nombre de chiffres du nombre de chiffres du nombre de chiffres du nombre de chiffres de n ne tiendrait pas sur votre feuille....

Or nous avons pu décrire N en 124 octets, ce qui veut dire que $$\tau (N)\le K(N)\le 124$$ alors que N est immense !

Tau est donc une fonction qui croît de manière inimaginablement lente.

En fait un nombre tel que N = ack(9,9) est un nombre très particulier, puisque malgré sa taille fabuleuse on peut le décrire en 124 octets (et encore moins avec une machine de Turing). De tels nombres sont précisément les nombres anti-aléatoires.

Quelques propriétés de K(n)

Le graphe de K(n) "oscille" donc entre des minimums successifs où elle touche tau(n), ce sont les nombres anti-aléatoires, et des maximums  (pour les nombres aléatoires) où elle est proche de log(n).

Mais les choses sont un peu plus complexes :

Pour des valeurs $m$ "proches" d'un nombre $n$,$ K(m)$ sera  très proche de $K(n)$. En effet, considérons par exemple $m=n+1$. Alors $m$ aura forcément une complexité  très proche de celle de n, puisque on peut décrire m par le programme "calculer n et imprimer n-1", un programme dont la longueur est presque la même que celle du programme "calculer n" qui est justement K(n).

La "pente" de la fonction K(m) est donc partout relativement faible. Et pourtant, presque tous les grands nombres sont aléatoires, et leur "Komplexité" est donc grande ! Mais il faut bien que, de temps en temps, la fonction K redescende jusqu'à son minuscule minimum $\tau (n)$... On commence à percevoir que ces "descentes" seront extraordinairement rares (bien qu'en nombre infini).

Que signifie "proche" dans un tel contexte ? Il est clair que $n+1,n-1,n+5,n/2,2n$... seront eux aussi considérés comme "proches" de n.  En fait, toute fonction injective $f$ sur les entiers dont la description est très courte par rapport à $K(n)$  peut convenir . Ainsi si $f$ est la fonction exponentielle, alors $exp(n)$ sera, en ce sens "proche" de $n$ puisque $K(exp(n))$ est très voisin de $K(n)$ !

Il en va de même de la fonction tau :

Pour des valeurs proches d'un nombre anti-aléatoire, la fonction K conserve des valeurs proches ; en effet si un nombre n est court à décrire, n+1, n-1, n+100000.... sont aussi des nombres dont la description sera courte. Aux alentours d'un nombre anti-aléatoire, là aussi, la pente de la fonction K est faible. Les nombres singuliers sont donc très peu nombreux, en effet s'ils étaient abondants le graphe de K "n'aurait pas le temps" de remonter jusqu'à son majorant log(n) et il n'existerait aucun nombre aléatoire : or ceux-ci sont pourtant "en moyenne" beaucoup plus nombreux que les nombres anti-aléatoires !

La fonction de Rado

Pouvons-nous trouver une fonction qui énumère tous les nombres anti-aléatoire ? Oui ! En fait cette fonction a déjà été inventée, dans un but différent, par un mathématicien hongrois nommé Tibor Rado.

La fonction Sigma(n) $\sigma (n)$ inventée par Rado est :

Soit $\sigma (n)$ la fonction qui associe à n le nombre le plus grand retournable par une fonction dont le code machine fasse moins de n bits.

Note technique : peu importe que nous comptions en bits ou en octets, de même peu importe que notre processeur soit une machine de turing ou une machine java, nous ne ferons que multiplier n et/ou sigma par des (petites) constantes, ce qui ne change pas qualitativement les résultats.

Si nous choisissons une machine de Turing, tau est la fonction qui donne le nombre minimal d'états de la machine nécessaire pour créer un programme qui imprime un nombre n ; et sigma est la fonction qui donne le nombre maximal que pourra imprimer un programme à n états. Sigma est parfois, dans le contexte des machines de Turing, appelée la "fonction du "castor affairé" J'ai consacré une page à ce sujet sur ce site.' castor affairé".

Il est clair que pour les premières valeurs de n, aucun programme de moins de n octets n'a une syntaxe correcte et donc $\sigma (0)=\sigma (1)=\sigma (2)...=0$

Mais ensuite sigma croît très vite : par exemple par définition noous avons vu que $\sigma (124)\ge ack(9,9)$ puisque on peut écrire en 124 octets un programme qui calcule ackermann(9,9) comme nous l'avons vu.

Et Sigma(125) est certainement encore bien plus grand que ack(99 ,9),un nombre tellement plus grand que ack(9,9) en fait, que cela donne le vertige. Je n'arrive tout simplement pas à imaginer un tel nombre. En fait, sigma est littéralement "la fonction qui croît le plus vite possible" au sens où au delà d'un certain rang n elle dépasse toute autre fonction (n dépend de la fonction).

Cela ne nous étonnera donc pas que sigma ne soit pas calculable, car il faut également être très futé pour trouver une fonction qui croisse "le plus vite possible". 

Soit un nombre n, par exemple 124 : nous savons que N = sigma(n) est un nombre gigantesque qui peut être décrit par un programme de 124 octets, et même nous savons que n ne peut pas être décrit par un programme plus court que 124 octets ; donc K(N) = 124.

Il s'en suit ce résultat très appréciable :

$\sigma (n)$ est, par définition, un nombre anti-aléatoire. Pour ces nombres singuliers, la fonction théta touche la fonction tau. Bien sûr d'autre fonctions, comme la fonction d'Ackermann ou la fonction factorielle produisent des nombres "presque singuliers", ces nombres presque singuliers se trouvant entre deux deux nombres singuliers. Nous pouvons donc préciser le graphe de la fonction K (nommée théta sur la figure ci-dessous)  :

La fonction théta atteint tau pour les valeurs successives de la fonction sigma ; entre deux de ces valeurs, elle est parfois proche de tau pour les nombres presque singuliers, et parfois (très souvent, en fait) proche de sa borne supérieure log(n) pour les nombres aléatoires.

Il faut bien voir que le graphe ci dessus est très trompeur : les valeurs sigma(1), sigma(2...) sont de plus en plus espacées, l'écart entre sigma10 et sigma11 étant par exemple presque infiniment plus grand que la valeur de sigma10 elle-même ! Dans notre schéma, l'échelle horizontale est donc distordue selon une sorte de "sigma-logarithme".

En regardant bien le graphe de K, on peut se demander si le comportement de la fonction entre sigma-i et sigma-i+1 n'est pas, en plus "riche", semblable à celui entre sigma-i-1 et sigma ; si c'est le cas, cela signifierait que la fonction K aurait une structure fractale, chaque intervalle [sigma(i), sigma(i+1)] étant semblable aux autres !

Remarquons que tau est l'inverse "à gauche" de la fonctions sigma :
$$\mathrm{\forall }n,\tau (\sigma (n))=n$$Le contraire n'est pas vrai : $\sigma (\tau (n))\ge n$,  et on a égalité seulement si n est un nombre anti-aléatoire.

Soit donc un nombre n, assez grand. Il existe une valeur k telle $\sigma (k)\le n\le \sigma (k+1)$. Cette valeur est tout simplement $\tau (n)-1$ puisque tau est par définition le minimum de toutes les valeurs de K(i) pour i >= n.

Pour prouver la "fractalité" de K, il faudrait trouver l'équivalent de "l'exponentielle-sigma", c'est à dire une fonction $F$ qui pour tout n  (compris entre $\sigma (k)$ et $\sigma (k+1)$) fournisse un entier $m=F(n)$ compris entre $\sigma (k+1)$ et $\sigma (k+2)$ et tel que $K(F(n))\sim K(n)$

En particulier, $F(\sigma (\tau (n)-1)=F(\sigma (\tau (n)))-1$, puisque $\tau (n)-1=k$ et que $K(\sigma (k))=k$ et $K(\sigma (k+1))=k+1$

Est-ce possible ? Cela fait un peu penser à la recherche de la fonction gamma, qui interpole la factorielle et la prolonge sur le continu...

A SUIVRE...