De l'esprit de la lettre de Chaitin au mot juste de Kolakoski

N. Lygeros




Selon la mentation développée par K. Gödel, A. Turing et Y. Matiajevic, qui a abouti à la découverte de G. Chaitin à savoir le nombre Ω via les notions d'incomplétude et d'indécidabilité, nous sommes en possession d'une immense liberté dans le domaine axiomatique. Cependant l'inconvénient de cette approche c'est qu'elle est essentiellement basée sur des constructions d'exemples artificiels. Cette situation ressemble quelque peu à celle des nombres transcendants qui sont omniprésents dans les nombres réels selon le fameux théorème de G. Cantor et qui sont si difficiles à trouver. Il est vrai que Liouville a trouvé rapidement des exemples de nombres transcendants comme celui que nous nommons le nombre de Liouville Σi10-i!. Cependant le véritable apport des idées cantoriennes n'a été perçu qu'avec la démonstration de la transcendance des nombres π et e i.e. des nombres non artificiels qui appartiennent à la tradition mathématique.

Ainsi dans la lignée des idées de K. Gödel qui avait proposé l'hypothèse de Riemann comme candidat en tant qu'entité non démontrable, G. Chaitin propose de considérer comme attaque possible la fonction de Möbius. De plus en s'appuyant sur les travaux de da Costa et Dovia qui ont montré que si ZFC est consistant alors P=NP est consistant avec ZFC, G. Chaitin propose aussi PNP comme autre candidat non démontrable. C'est en ce sens là que nous voulons proposer pour notre part un exemple qui provient du monde combinatoire et en particulier de la théorie des mots. Pour définir le mot de Kolakoski nous n'avons besoin que de très peu de matériel : Un alphabet composé uniquement de deux lettres 1 et 2, de la notion de bloc qui est une concaténation de lettres identiques et de la définition du mot : la valeur de la nième lettre est égale à la longueur du nième bloc. Si nous nommons wk le mot qui commence par la lettre 2, il est trivial de voir que celui qui commence par la lettre 1 s'écrit sous la forme 1 wk. De plus il est clair qu'il existe un algorithme qui permet de décider si la nième valeur de wk est un 1 ou un 2. Par contre si nous recherchons quelle est la longueur moyenne du nième bloc nous entrons dans un domaine beaucoup plus complexe. En effet les calculs sur ordinateurs montrent avec une précision finie aussi grande que l'on désire que la valeur est égale à 3/2 sans pour autant que cela soit démontré. Il est vrai que ce fait s'explique par l'équiprobabilité d'apparition des lettres 1 et 2. Cependant dans la répartition de ces lettres se cache un résultat curieux. D'une part nous ne savons pas démontrer l'existence d'une limite pour le rapport du nombre de 1 sur le nombre total. D'autre part Chvátal n'a pu démontrer que le résultat suivant : si la limite existe alors celle-ci est très proche de 1/2.

Pour le moment nous ne connaissons pas quelle est la complexité du mot de Kolakoski. Aussi l'ensemble de ces données suggèrent qu'il serait possible d'envisager l'égalité à 1/2 de la limite possible comme un candidat en tant que proposition naturelle non démontrable puisque la structure autoréférente du mot de Kolakoski n'est pas sans rappeler l'approche de K. Gödel pour ouvrir les voies de la liberté axiomatique.







free counters


Opus