Auteur: Serge Boisse
Date: Le 27/03/2023 à 13:03
Type: web/MOC
Tags: maths,autoréférence,fonction
pub: oui
commentaires: ouiCopier

L'univers est-il autoréplicateur ? La fonction qui se commente elle-même, et ce qui en découle

Contenu de cette page :

Un petit exercice pour vous détendre
Notre jeu concours
Quel rapport avec la cosmologie ?
Commentaires sur la guerre des Codes
Le principe anthropique
Une suite de programmes croissants en moyenne
Analyse de la situation
Un univers fractal

Un petit exercice pour vous détendre (si vous aimez la programmation et l'autoréférence)

Suivez ce lien (autorep) ! Il comporte également notre jeu-concours !

Quel rapport avec la cosmologie ? Ce n'est pas simple à trouver, mais réfléchissez un peu , ça vous fera du bien ;-)

Il est possible de comparer l'univers à un processus : on décompose le temps en intervalles, éventuellement très courts (par exemple un intervalle égale au temps de Planck, 10-43 secondes). Le processus en question consiste alors, pour un état donné de l'univers à l'instant t, à calculer l'état à l'instant t+1.

C'est donc bien un processus parfaitement défini, à condition que ce qu'on entend par "état de l'univers" soit également défini. Les afficionados de la mécanique quantique m'objecteront que l'univers n'est pas déterministe et qu'un tel "état" ne saurait exister. Certes, mais la théorie de la relativité fractale énonce que l'indéterminisme n'est qu'une conséquence de la relativité des échelles, et qu'à une échelle donnée on peut parfaitement avoir un déterminisme local. De plus, l'indéterminisme ne se manifeste que lors de l'observation d'un processus par un observateur : l'équation de Schrödinger est, elle, parfaitement déterministe. Dans le cas de l'évolution cosmologique, il ne saurait exister un observateur en dehors de l'univers.... Sinon, si on arrivait à le prouver, cela aurait quelques conséquences théologiques qui feraient du bruit !La question est donc d'importance.

Supposons donc que l'univers est un processus : la première question, est : sur quel genre de CPU tourne-t-il et avec quel OS? (non, pas windows 98 !!! ;-) Plus sérieusement, des travaux de David Deutsch on montrés que les "ordinateurs quantiques" sont plus performants que les ordinateurs classiques qui sont tous équivalent à la machine de Turing : un ordinateur quantique a la possibilité de travailler non sur des états d'un système mais sur des superpositions d'états, c'est à dire qu'il est intrinsèquement parallèle avec une infinité de CPUs "SIMD" (single instruction, multiple datas).

David Deutch a quand même montré qu'il y avait des limites, notamment le fait que bien que l'ordinateur quantique fasse effectivement une infinité de calculs simultanément (ce qu'on peut prouver lorsque ces calculs interfèrent) , l'observation de cet ordinateur produit une réduction du paquet d'ondes et seul un résultat est disponible en sortie... (en fait une combinaison linéaire de résultats, mais bon...) David Deutch a défini ce à quoi ressemblait une machine de Turing quantique. voilà donc notre processeur !

Quel est le point de départ de ce processus ? Le début de l'univers ! Il semble opportun alors de se référer au crédo des tenants du big bang, ou encore à la Bible : au commencement il n'y avait Rien.

Mais rien, c'est déjà quelque chose puisqu'on peut l'écrire :

rien

et voilà notre premier programme !

// programme univers-1
class Univers {
 public static void main(String argv []) {
    System.out.println("rien");
  }
}
Copier

J'ai écrit ce programme en java, car si le CPU universel ne sais pas faire tourner java, c'est qu'il est nul ! ;-)

Ce programme, lorsqu'on l'exécute, ne fait rien qu'à produire du rien : il écrit le mot "rien" et s'arrête. Mais ce n'est qu'un début, n'est-ce pas ? En fait, au lieu de "rien" j'aurais pu choisir la chaîne vide ""...

Remarquons qu'il existe une infinité de programmes susceptibles de faire la même chose, par exemple :

// programme univers-3141592653589793
class Univers {
 // on fait rien qu'a perdre du temps
 for (int i=0; i< 3141592653589793; i++) 
   {int j = i;}
 public static void main(String argv []) {
    System.out.println("rien");
 }
}
Copier

Le fait que ce dernier programme passe pas mal de temps à ne rien faire ne doit pas nous effrayer : le créateur a tout son temps puisqu'il existe en dehors de l'univers en un lieu où le temps n'existe pas !

Nous verrons plus loin comment on s'accommode d'une telle variété. Pour l'instant, contentons-nous de choisir l'un de ces programmes au hasard, par exemple le premier que j'ai cité. (univers 1)

Commentaires sur la guerre des Codes

Et maintenant, que fait le créateur ? Il se repose ? que nenni : il se rend compte qu'il vient de créer non plus "rien", mais un programme qui crée ce "rien". Ca mérite bien un petit commentaire, non ?

// univers-1.1
class Univers {
 public static void main(String argv []){
    System.out.println(
     "class Univers {\n"+
     " public static void main(String argv[]){\n"+
     "    System.out.println(\"rien\");\n"+
     "  }\n"+
     "}");
  }
}
Copier

Que fait ce programme ? il imprime le premier ! Autrement dit, en exécutant univers 1.1, on obtient univers 1, et en exécutant ce dernier, on obtient univers 0, c'est à dire "rien"... Remarquons qu'il y a avait aussi une infinité de façons de commenter univers 1, et j'aurais même pu écrire un programme univers-1.2 plus court que univers-1.1, mais moins lisible...

Vous commencez à voir l'idée générale : rien ne nous empêche maintenant de commenter aussi univers-1.1 !

// univers-1.1.1
class Univers {
 public static void main(String argv []) {
    System.out.println(
     "class Univers {\n"+
     " public static void main(String argv[]){\n"+
     "    System.out.println(\n"+
            "\"class Univers {\\n\"+\n"+
            "\" public static void main(String argv[]){\\n\"+\n"+
            "\"    System.out.println(\\\"rien\\\");\\n\"+\n"+
            "\"  }\\n\\"+\n"+
            "\"}\");\n"+
     "  }\n"+
     "}");
  }
}
Copier

Notons que ça commence à être fichtrement compliqué à cause de tous ces blackslash '' qui viennent s'incruster méchamment dans le code comme la vérole sur le bas clergé. Notons donc "citer" (quote en anglais) l'opération "prendre une chaine, insérer un caractère backslash devant tous les caractères guillemet '"', quote ''' ou backslash '' dans cette chaine, puis entourer le résultat par des guillemets". (En fait, ce mode opératoire compliqué vient de la façon dont java (mais aussi C et C++) traitent les chaînes). Par exemple :

citer("rien") vaut "rien" (avec les guillemets), mais  
citer(citer(rien)) vaut "\"rien\"", quand à  
citer(citer(citer("rien"))) il vaut ... 
	"\"\\\"rien\\\"\"" ce qui n'est pas si facile à trouver !``
Copier

Nos univers successifs sont quasiment des citations l'un de l'autre.

Comme à chaque étape correspond une infinité de programmes possibles, nous obtenons un arbre d'univers dont chacun cite le précédent :

1.1.2 cite 1.1

Il nous faut donc un principe pour sélectionner, à un niveau donné, le "bon" univers. Je propose donc, de manière tout à fait arbitraire le principe suivant :

A chaque niveau > 0, il existe une infinité d'univers. L'un des ces univers sera dit "réel", les autres seront "virtuels". Ces univers sont construits en commentant les univers virtuels ou réels du niveau précédent:

Principe de la sélection de l'univers réel :

l'univers réel sera l'univers le plus court en taille à ce niveau de commentaire.

Ainsi dans la figure ci-dessus, au niveau 2 l'univers "réel" pourrait être 1.343, et au niveau 3 ce pourrait être 666.1.1 : les univers réels successifs ne sont pas forcément parents l'un de l'autre !

Le principe anthropique

Notons que ce principe n'est pas le seul possible, par exemple on aurait pu dire "univers-N+1 est le plus court programme qui commente univers-N"

Nous voyons ici se profiler la main du créateur d'univers, qui seul peut choisir la règle à appliquer... Mais c'est précisément ici que le jeu devient intéressant : Nous avons besoin d'un règle pour sélectionner un univers, et nous pouvons chercher des "méta règles" qui limiterons les règles possibles.

Une méta-régle est par exemple : l'univers réel au niveau n est un programme qui doit générer le listing d'un autre programme : en exécutant ce second programme, on obtient un troisième programme.... tels que en répétant la procédure n fois on obtienne "rien" .

Une autre méta-rè;gle possible est que nos univers doivent être "raisonnables", ou encore "intéressants", c'est à dire ni trop simple ni trop compliqués. Ceci est évidement plus compliqué à formaliser. Nous y reviendrons.

D'autres méta-règles pourraient régir la taille des univers successifs : on pourrait exiger qu'elle soit croissante (mais est-ce intéressant ?) ou encore qu'une fonction calculable à partir de la description d'un univers soit croissante : on pense à une pseudo-entropie... Nous y reviendrons également

Toutefois, puisque nous nous attachons à décrire quelque chose qui "pourrait" être l'univers dans lequel nous vivons, nous pouvons exhiber quelques points intéressants :

• Il faudra définir des fonctions qui, à partir de "l'univers-programme", "miment" certaines caractéristiques d'un univers physique : comment, dans un programme définir des notion d'espace, de temps, d'énergie.... Nous y reviendrons bien sur !
• L'univers doit inclure la notion d'observateur ! Puisque nous somme dans l'univers physique, c'est que cet univers physique admet la présence d'observateurs. Ceci est un principe très fort connu sous le nom de principe anthropique : il permet de limiter les univers possibles théoriquement d'une manière drastique.

Pour le moment, jouons déjà avec la règle (unique) que nous nous sommes fixés, nous verrons ensuite si en comment on peut la faire varier.

Une suite de programmes de longueur moyenne croissante

Continuons donc avec la règle que nous avons choisie : L'univers réel est l'univers le plus court à ce niveau de commentaire : l'univers réel au niveau n+1 est donc le programme le plus court qui commente l'un des univers virtuels au niveau n.

Au niveau zéro, il y n'y a rien, et donc ce rien est l'univers réel ("réel-0").

Au niveau 1, le programme le plus court est facile à trouver : c'est un programme qui cite (au sens ci dessus) univers-0. C'est donc le programme univers-1, mais sans la mise en page qui le rendait agréable à lire : appelons-le univers-1bis

Aux niveau 2, il est probable que le programme le plus court est celui qui cite univers-1bis, (appelons-le univers-1bis-1) et de même au niveau 3. Par conséquent réel-1 est parent de réel-2 qui est parent de réel-3.

Mais ensuite, les choses se gâtent à cause du programme suivant , réellement diabolique :

// diabolic-3
class diabolik {
 static String commente(String s) {
     if (s.length() == 0)
       return "";
     StringBuffer q = new StringBuffer();
     for (int i=0; i<s.length(); i++) {
       char c = s.charAt(i);
       if (c=='\\' || c=='\"' || c== '\'')
         q.append('\\');
       if (c =='\n')
         q.append("\\n\"+\n\"");
       else q.append(c);
     } // for
     return "class univers {\n public static void main(String argv[]){\n System.out.println(\""+q+"\");\n }\n}"; 
 }
 static String nq(int n) {
     String r = "rien";
     for (int i=0; i<n; i++) r=commente(r);
     return r;
 }
 public static void main(String argv[]){
     System.out.println(nq(3));
 }
}
Copier

Que fait ce programme ? Il affiche univers-1.1.1 !! Autrement dit, c'est un bon candidat pour être univers-1.1.1.1 ; mais il y a plus : si j'avais écrit sur la dernière ligne : nq(1000000) au lieu de nq(3), diabolik m'aurait imprimé (après un certain temps ;-) un programme de plusieurs millions de lignes, et en exécutant ce programme j'aurais obtenu un programme un peu plus court qu'en exécutant... Eh oui ! En répétant un million de fois la procédure, je serais retombé sur univers-1 !

Il n'y a pas de miracle : la fonction "commente" effectue exactement cela, le commentaire d'un programme (en gérant correctement toutes ces histoires de backslash) et la fonction "nq" exécute n fois le commentaire de "rien".

Il s'en suit que la taille de univers-1000000 est plus petite que celle de diabolik-1000000, soit seulement 669 octets ! La taille de univers-un-milliard est, elle, inférieure à 672 octets...

L'univers croît donc extrêmement lentement.

Et ce n'est rien de le dire ! En fait, il croît littéralement plus lentement que tout ce qui est imaginable.

Qu'est-ce que cela veut dire ? Il est clair que nous pouvons majorer la taille de l'univers-n par celle de diabolik "vide" : 666 octets ;-) plus le nombre d'octets nécessaire pour écrire n. Quel est ce nombre d'octets ?

Tout d'abord, précisons un point : nous allons dorénavant utiliser une version légèrement modifiée de java, dans laquelle le type "int" a une précision arbitraire, c'est à dire que un 'int' pourra être aussi long que l'on veut. Ceci reste sans conséquences qualitative sur la théorie à cause du principe d'équivalence entre les machines de Turing universelles. Au besoin on pourrait parfaitement écrire des nombres arbitrairement grand en java standard moyennant une convention de représentation, par exemple utiliser des vecteurs d'entier ou même des structures hiérachisées à plusieurs niveaux capables de représenter des nombres arbitrairement grand, de plusieurs milliards de milliards de chiffres (et nous verrons que nous seront contraint tout à l'heure d'envisager des nombres encore beaucoup plus grands que ceux-là !) ; la seule conséquence serait que nous devrions remplacer "666" par un nombre un peu plus grand, disons 2001 ;-).

Considérons maintenant une version un peu modifiée de diabolik , écrite dans notre version modifiée de java (mais bien sur tout autre langage ou même une machine de Turing aurait fait l'affaire) :

// diabolic-NT
class diabolik {
 static String commente(String s) {
   // MEME CODE QUE DANS DIABOLIK
 }
 static String nq(int n) {
     String r = "rien";
     for (int i=0; i<n; i++) r=commente(r);
     return r;
 }
 static int retourne_n() {
   // CODE A REECRIRE POUR CHAQUE N
 }
 public static void main(String argv[]){
     System.out.println(nq(retourne_n()));
 }
}
Copier

Dans cette version modifiée, j'ai ajouté une fonction "retournen" qui est censée retourner un nombre n arbitrairement grand. Le code de retourne-n sera différent pour chaque n : Par exemple, retourne_n pourrait calculer la factorielle de un million et retourner ce nombre : il est clair que le programme diabolik-NT ainsi conçu sera plus court que le programme diabolik-1000000! correspondant. On impose de plus la condition suivante : _La taille de la fonction retourne_n pour un n donné doit être minimale. Autrement dit, pour un n donné, disons 1000000! le programme retourne_n doit être le programme le plus court en taille qui retourne ce nombre.

Définition : fonction théta(n)

Soit donc theta(n) la fonction qui donne la taille du code du programme le plus court qui retourne n.

Ainsi, nous pouvons affirmer que

La taille de univers-n est inférieure à 700 + theta(n).

(700 est la taille de diabolik-NT)

Or theta(n) est une fonction passablement curieuse. C'est la fonction qui donne la complexité de Chaitin-Kolmogorov d'un nombre entier.

Tout d'abord, c'est une fonction non calculable. Ceci veut dire qu'il n'existe aucun programme prenant n en argument et imprimant theta(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 theta(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 theta(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 theta 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 theta 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 theta ne soit pas calculable nous dit simplement que theta 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 ; theta é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 theta(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 :

theta(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, theta(n) ~= Log10 n. La fonction theta 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

theta(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 theta(i). Tau est la fonction qui relie "par en dessous" les minimum successifs de la fonction theta.

Pour tout n, théta(n) >= tau(n) ; en effet tau(n) = min(theta(n), tau(n+1)) <= theta(n).

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

Enfin, tau est une fonction croissante : tau(n) = min(theta(n), tau(n+1)) <= tau(n+1), et
lim n->+oo tau(n) = +oo.

Nous avons donc un minorant de theta qui est une fonction croissante, non bornée, qui atteint theta un nombre infini de fois. Ceci donne une première indication de l'allure du graphe de theta :

Un 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 :

  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'ergottons 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 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 ) <= théta(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 méritent une définition :

Définition : nombre singulier

On appellera nombre singulier tout nombre n dont la description peut se faire en un nombre de bits voisin de tau(n).

Ces nombre singuliers sont le pendant ou si l'on préfère le contraire des nombres aléatoires dont la description exige un nombre de bits proche de log(n). Pour un nombre singulier, theta(n) ~= tau(n). Pour un nombre aléatoire, theta(n) ~= log n.

Nous avons donc encadré (à une constantes près) theta entre deux fonctions croissantes, tau(n) et log(n) . La fonction theta "oscille" entre ces deux extrêmes mais sans faire trop de zèle (i.e avec une pente finalement assez faible).

Analyse de la situation :

Revenons à nos univers qui se commentent les uns-les autres :

Les programmes du genre "diabolik" sont très probablement les programmes les plus courts qui décrivent l'univers au dela d'un certain rang : par exemple en insérant le code qui retourne N=ack(9,9) dans le code de diabolik-NT, on obtient un programme assez court (824 octets) qui peut être le point de départ d'une suite de N programmes se commentant les uns-les autres pour converger finalement vers "rien". Or N, nous l'avons dit, est un nombre dont la taille défie l'imagination et même la raison. C'est un "nombre singulier", un nombre dont la description est très courte devant sa taille (son nombre de chiffres).

Pour des valeurs proches d'un nombre n singulier, la fonction theta 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 singulier, la pente de la fonction theta est faible. Les nombres singuliers sont donc relativement peu nombreux, en effet s'ils étaient abondants le graphe de theta "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 singuliers !)

Nous allons introduire encore une nouvelle fonction (promis, ce sera la dernière !) afin de préciser encore un peu l'allure de theta(n) et tau(n) : la fonction sigma(n), que nous allons définir tout simplement comme "la fonction qui retourne la valeur la plus grande possible".

Définition : sigma(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 : c'est ce que l'on appelle la fonction de rado, d'après son inventeur Tibor Rado.

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), nombre tellement plus grand que ack(9,9) 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". Sigma est parfois, dans le contexte des machines de Turing, appellée la "fonction du castor affairé".

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 theta(N) = 124.

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

pour tout n, tau(sigma(n)) = theta(sigma(n)) = n

sigma(n) est, par définition, un nombre singulier. Pour ces nombres singuliers, la fonction théta touche la fonction tau. Bien sur d'autre fonctions, comme la fonction d'ackermann ou la fonction factorielle produisent des nombres "presque singuliers", ces nombres presques singuliers se trouvant entre deux deux nombres singuliers. Nous pouvons donc préciser le graphe de la fonction théta :

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 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 des n est donc distordue selon une sorte de "sigma-logarithme".

En regardant bien le graphe de théta, 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 sigma (et donc aussi la fonction "univers") aurait une structure fractale, chaque intervalle [sigma(i), sigma(i+1)] étant semblable aux autres !

En fait nous pouvons dire plus sur théta(n), la fonction qui retourne la complexité de chaitin-Kolmogorov du nombre n :

D'abord, pour tout n, theta(2n) <= theta(n)+2

il suffit de mettre "return theta(n)*2" au lieu de "return theta(n)".
Naturellement, theta(n/2) <= theta(n) A cause de "return theta(n)/2"

Par suite de ce qui précède, theta(n) - 2 <= theta(2n) <= theta(n+2)

Mais bien sur au lieu de 2, on aurait pu mettre 9, 99, 99999999... En fait tout nombre k que l'on peut écrire en décimal en log10k chiffres.

On obtient :

theta(n) - log10k <= theta(k.n) <= theta(n) + log10k

Et en fait on pourrait remplacer ci dessus l'opérateur multiplication (le point dans theta(k.n)) par n'importe quelle opérateur .,/,+,- inversible implémenté dans le langage.

Mais en fait on peut faire encore mieux :

Si nous codons dans notre programme-univers deux fonctions retourne_n différentes : soit retourne_n() une fonction de longueur ln qui retourne un nombre n (donc ln = theta(n)) , et retourne_p() une fonction de longueur lp qui retourne un nombre p (donc lp =theta(p)), alors :

L'expression "retourne_n() + retourne_p()" retourne n+p et a une longueur de 26 octets ; par suite la complexité (le theta) de n+p est inférieur à ln+lp+26, où ln et lp sont les complexité de n et de p. Bien sur la complexité de n-p, n*p, et n/p est identique.

Remarque : en donnant à mes fonctions des noms plus court, j'aurais obtenu un nombre différent (inférieur) à 26 ; en fait peut importe, ce qui compte c'est qu'il existe une constante k indépendante de n et p, et relativement petite, telle que la propriété
théta(n .op. p) < théta(n) + theta(p) + k reste vraie (.op. est l'un des quatre opérateurs +,-,.,/)

Autre remarque la complexité d'un nombre négatif -n est la même ou presque la même (à 1 prés pour mettre le signe '-') que celle de n ; donc theta(n-p) = theta(p-n) à 1 près / si nous ajoutons 1 à k , nous pouvons donc considérer valablement des expressions telles que theta(n-p) avec p > n.

Donc pour tout n et p entiers relatifs quelconques :

theta(n) = theta(n-p+p) < theta(n-p) + theta(p) + k
theta(n-p) > theta(n) - theta(p) -k
theta(n) = theta(n+p-p) < theta(n+p) + theta(p) + k
theta(n+p) > theta(n) - theta(p) - k

d'où : il existe k (inférieur à 26) tel que pour tout opérateur binaire inversible .op. du langage et pour tout n et tout p :

theta(n) - theta(p) - k < theta(n .op. p) < theta(n) + theta(p) + k

En particulier si p = sigma(s) (donc theta(p) = s) alors :

theta(n) - s + k < theta(n .op. sigma(s)) < theta(n) +s + k

Le nombre sigma(s) étant un nombre gigantesque devant s, on mesure ici la très faible variation de la fonction théta ! C'est en ce sens que l'on peut dire que la fonction se "reproduit" aux voisinage des sigma(s). successifs. Mais attention : si nous considérons un nombre p qui n'est pas "proche" d'un sigma(s), alors l'expression theta(n .op. p) n'a aucune raison de rester proche de theta(n).

Nous n'avons pas une véritable autosimilarité aux voisinage des sigma(s) (elle est exacte à k+s près) mais nous avons quand même un comportement fractal !

Un univers fractal

Notre univers numérique débouche donc sur un univers fractal, presque autosimilaire : au voisinage des sigma(s) quand s parcours l'ensemble des entiers naturels, la fonction théta (complexité de Kolmogorov-Chaitin) reste presque identique ! chaque s ajoute simplement un niveau de détail supplémentaire...

La question que se pose tout de suite est : quelle est la dimension fractale du graphe de la fonction théta ? Etant donné le très faible taux de variation de theta(n), on pourrait penser que cette dimension fractale est proche de 1.

Mais d'autre part, on sait que "entre" les point n=sigma(s) successifs, la fonction varie entre s et log(n) et donc elle n'est pas une fonction "calme" : le paradoxe provient de ce que les intervalles |sigma(s), sigma(s+1)] successifs sont de plus en plus gigantesques et croissent inimaginablement vite.

La fonction d'autosimilarité A qui à n associe le plus petit p supérieur à n tel que le comportement de theta au voisinage de n soit (presque) identique au comportement au voisinage de p croît elle aussi très vite ; en fait elle croît comme sigma, car A(sigma(s)) = sigma(s+1).

Pour trouver A, nous sommes dans une situation semblable à celle qui intriguait les mathématiciens du siècle dernier lorsqu'ils cherchaient la "bonne" fonction de la variable réelle qui reproduisait le comportement de la fonction factorielle. (ceci déboucha sur la fonction gamma, telle que pour out entier n , n! = gamma(n+1)). La différence est que ici nous devons trouver une fonction qui "interpole" sigma(n) et non factorielle(n).

Supposons que cette fonction A existe : alors theta(A(n)) ~ theta(n). Nous pouvons considérer une injection de l'ensemble des entiers dans lui même, et déterminer une relation d'équivalence pour des points mis en relation par A. Le graphe de theta(n) se ramifie alors de plus en plus et devient de plus en plus serré, si bien que nous aboutissons au résultat surprenant :

La dimension fractale du graphe de sigma(n) est 2 exactement.

(Du moins j'en ai l'intuition : un démonstration suivra prochainement).

L'élément intéressant, c'est que cette dimension 2 est précisément celle qui émerge en relativité d'échelle....

(A SUIVRE, RESTEZ A l'ECOUTE, PROCHAINEMENT DES DEVELOPPEMENTS DE LA THEORIE)

> La suite : créez un "autorep" !
< page précédente : Un univers graphe