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).
K(n) sera la taille que prend la description la plus courte possible du nombre n. Mais qu'est ce qu'une description ? Si l'on veut que cette description soit claire et non-ambiguë, on prendra un langage informatique quelconque et l'on posera que K(n) est la taille du plus court programme informatique dans ce langage dont le résultat, une fois imprimé ou écrit sur un écran, sera le nombre 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 K1(n) est la taille du plus court programme (qui imprime n) dans le langage 1, et K2(n) est la taille du plus court programme (qui imprime n) dans le langage 2, alors le rapport k1(n)/K2(n) restera compris entre des limites bornées 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.
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 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 que les nombres aléatoires seront ceux pour lesquels K(n) est proche de log(n), qui est "le nombre de chiffres de n".
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) ~= 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+Log10 n. Par conséquent :K(n) < 8+Log10 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) ~= Log10 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)
Considérons la fonction n->tau(n) = minimum pour i=n à +oo de K(i).
Tau est la fonction qui relie "par en dessous" les minimum successifs de la fonction K.
Pour tout n, K(n) >= tau(n) ; en effet tau(n) = min(K(n), tau(n+1)) <= K(n).
Tau est donc un minorant de K. C'est de plus un "bon" minorant : en effet quel que soit n, tau(n+1) = min pour i > n de 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)) <= tau(n+1), et
lim n->+oo tau(n) = +oo.
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
Les nombres anti-aléatoires n sont précisément ceux dont la complexité de Kolmogorov K(n) est très petite devant log(n), et donc proche de tau(n), c'est à dire ceux pour lesquelsK(n) ~= tau(n).
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);}
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 (comme toute fonction calculable croissante) un majorant de tau.Pour donner une idée du nombre que renvoie la fonction retourne_n() , appelons le N (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) <= K(N) <= 124
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) inventée par Rado est :
"la fonction qui retourne la valeur la plus grande possible pouvant se décrire par un programme de longueur n".
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, appellée la "fonction du 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) = ... = 0.
Mais ensuite sigma croît très vite : par exemple par définition sigma(124) >= 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 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 :
Théorème :
pour tout n, tau(sigma(n)) = K(sigma(n)) = n
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 : pour tout n,
tau(sigma(n)) = n
Le contraire n'est pas vrai : sigma(tau(n)) >= 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 que n est compris entre sigma(k) et 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) tel que K(F(n)) ~ 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...
Partagez / votez pour cette page :
Jeu de briques
Snake
Pacman
Bubble