suite de Kolakoski

Regroupez le début 2211212212211… en paquets de chiffres identiques : 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11… Puis comptez les chiffres de chaque paquet. Les tailles obtenues sont 2, 2, 1, 1, 2, 1, 2, 2… : c'est précisément le début que l'on vient de lire.

La suite de Kolakoski décrit ainsi sa propre découpe. Ses chiffres jouent deux rôles à la fois : ils forment le mot et indiquent combien de fois le même chiffre doit être répété dans chaque bloc successif.

La suite de Kolakoski est un mot infini K formé uniquement avec les symboles 1 et 2. Un bloc maximal est une suite de symboles identiques que l'on ne peut prolonger ni à gauche ni à droite avec le même symbole. Au début de K, la découpe est 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11…

Si l'on remplace successivement chaque bloc maximal par sa longueur, on obtient 2, 2, 1, 1, 2, 1, 2, 2… La propriété qui définit K est que cette suite de longueurs redonne K elle-même : $\mathcal{R}(K)=K\backslash mathcal\{R\}(K)=K$, où la lettre R désigne l'opération qui relève les longueurs des blocs. Comme les blocs sont maximaux, leurs symboles alternent nécessairement entre 2 et 1. Puisque cette suite de longueurs est égale à K et que les termes de K appartiennent à l'alphabet {1, 2}, chaque bloc a une longueur égale à 1 ou à 2.

Avec la convention retenue ici, K commence par 22. Ces deux premiers termes fixent les deux premières longueurs : on écrit donc 22, puis 11. Les termes déjà produits donnent ensuite, dans l'ordre, la longueur des blocs suivants. William Kolakoski a proposé cette suite en 1966. La question de la fréquence respective des deux symboles dans le mot infini demeure non résolue d'après la définition source.

Quatre éléments sont indispensables. L'alphabet fournit les deux symboles 1 et 2. Le mot infini les place dans un ordre précis. Les blocs maximaux découpent ce mot chaque fois que le symbole change. Enfin, la suite des longueurs remplace chaque bloc par le nombre de symboles qu'il contient. Dans K, ces longueurs valent 1 ou 2 parce que cette suite redonne K elle-même.

L'ordre du mot détermine donc les frontières des blocs, puis ces frontières déterminent leurs longueurs. La dépendance remarquable va aussi dans l'autre sens : les longueurs, lues comme les termes de K, commandent la taille des blocs à produire. L'alternance des symboles indique leur contenu ; les termes de K indiquent leur taille. Ensemble, ces données suffisent à prolonger le mot pas à pas.

Construisons et contrôlons les vingt premiers termes. Les données sont l'alphabet {1, 2}, le début 22, l'alternance des symboles de bloc 2 puis 1, et la règle selon laquelle le terme lu donne la longueur du bloc correspondant.

1. Les deux premiers termes valent 2 et 2. Les deux premiers blocs ont donc chacun une longueur de 2 : 22 | 11.

2. Les termes suivants déjà visibles sont 1 puis 1. On ajoute un seul 2, puis un seul 1 : 22 | 11 | 2 | 1.

3. En continuant à lire les termes produits et à alterner le symbole des blocs, on atteint vingt termes : 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | 2 | 11 | 22 | 1 | 2. La figure aligne ce mot et le relevé de ses blocs.

4. Leurs longueurs sont 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1. Ce relevé est exactement le préfixe de treize termes 2211212212211 du mot construit. Le terme suivant, le vingt-et-unième, vaut 1 : le dernier 2 affiché est donc bien un treizième bloc complet, et non l'annonce d'un quatorzième bloc achevé.

Pour vérifier un préfixe, séparez-le à chaque changement de symbole, comptez les termes de chaque bloc complet, puis comparez cette liste au début du préfixe. Si une longueur diffère, le mot testé n'est pas un préfixe de la suite avec la convention 22.

Pour prolonger la suite, gardez un pointeur sur le prochain terme à lire. Ce terme vaut 1 ou 2 : ajoutez autant d'exemplaires du symbole opposé à celui du dernier bloc, puis avancez le pointeur. Une simple répétition périodique ne convient pas, car la longueur à ajouter doit toujours être relue dans le mot en cours de construction.

Pour étudier les fréquences, comptez séparément les 1 et les 2 dans des préfixes de plus en plus longs. Ces calculs donnent des observations finies ; pour répondre à la question sur le mot infini, il faudrait établir l'existence d'une fréquence limite et sa valeur.

Termes du mot et longueurs des blocs. Les premiers sont les symboles placés aux positions successives ; les secondes comptent les symboles identiques dans chaque bloc maximal. Dans le préfixe 2211, le troisième terme est 1, tandis que le troisième bloc est le seul symbole 2 qui suit 2211 et sa longueur vaut aussi 1. Les valeurs coïncident dans le même ordre, mais elles n'indexent pas les mêmes objets.

Auto-description et simple répétition. Répéter mécaniquement 2211 donne 22112211… ; ses blocs ont tous une longueur de 2, donc leur relevé commence par 2222 et ne reproduit pas le mot. Pour reconnaître Kolakoski, il faut comparer le mot entier à la liste ordonnée de ses longueurs de blocs, pas seulement repérer un motif qui revient.

Bloc final d'un préfixe. Couper le mot au milieu d'un bloc fait paraître ce dernier plus court. Pour contrôler un préfixe fini, ne validez sa dernière longueur que si le changement de symbole suivant est connu ; les blocs précédents, eux, sont complets.

Convention initiale. La fiche emploie la version qui commence par 22. Modifier le début change la construction observée. Il faut donc annoncer les premiers symboles avant de comparer deux listes ou deux programmes de génération.

Fréquence observée et fréquence limite. Parmi les vingt premiers termes affichés, on compte onze 2 et neuf 1. Ce rapport fini ne résout pas la question mentionnée dans la source : une fréquence dans le mot infini exige une limite lorsque la longueur du préfixe croît, et cette limite ne peut pas être déduite d'un seul échantillon.

La suite invite à étudier les points fixes d'une transformation : ici, relever les longueurs des blocs laisse le mot inchangé. Cette perspective conduit à demander quelles autres suites peuvent être auto-descriptives lorsque l'on change l'alphabet ou la convention de départ.

Une seconde piste consiste à comparer des préfixes de tailles croissantes. Le comptage expérimental des symboles, la répartition des blocs et leurs fluctuations fournissent des indices, tout en laissant entière la nécessité d'une preuve sur le comportement infini.