|
|
|
|
Un mot est une succession, finie ou non, de symboles (généralement appelé lettres) pris dans un certain alphabet :
En repérant les répétitions, on peut découper un mot en blocs :
En écrivant bout à bout les longueurs de ces blocs, on obtient un nouveau mot formé de nombres :
Ce deuxième mot peut être appelé la lecture du premier.
Si les symboles de l'alphabet représentent des nombres, il se peut que certains mots coïncident avec leur lecture. Kolakoski a donné en 1966 le premier exemple de ces "self reading words", avec l'alphabet {1,2} :
Déterminons un tel mot en supposant qu'il commence par le chiffre 2. Ce "2" en lecture signifie que le mot doit commencer par un bloc de 2 symboles identiques ; le début du mot est donc, nécessairement :
2 2 1
le second chiffre 2 indique la présence d'un bloc de 2 symboles qui succède au premier bloc ; après le bloc 22 le mot se poursuit donc par 112 Nous voici donc avec le début :
2 2 1 1 2
Le troisième symbole de cette suite indique que le troisième bloc du mot est de longueur 1, ce qui permet de trouver le symbole suivant. Le procédé de construction se poursuit ainsi, indéfiniment :
2 2 1 1 2 1 2 2 1 2 2 1 1 Š
Cette suite, illimitée, est bien formée de 2 chiffres 2, 2 chiffres 1, 1 chiffre 2, 1 chiffre 1, 2 chiffres 2, 1 chiffre 1, 2 chiffre 2, 2 chiffres 1, etc.
Sa lecture est donc bien
2 2 1 1 2 1 2 2 ...
c'est à dire ... elle-même ! Le mot infini obtenu est connu sous le nom de suite de Kolakoski. Plus généralement, en l'honneur de l'inventeur, nous appelons mot de Kolakoski tout mot qui est sa propre lecture.
Le sujet
Malgré la simplicité de sa fabrication (que nous vous invitons à justifier plus rigoureusement par vous même), la suite de Kolakoski reste bien mystérieuse.
On se demande en particulier si les chiffres 1 et 2 apparaissent aussi souvent l'un que l'autre dans cette suite.
|
|
La question se généralise aux mots de Kolakoski :
Quelques entrées possibles
A quoi cela sert-il ? ... billards, nombres, automates et chaos
Lançons une boule dans un billard carré qui va indéfiniment rebondir sur son bord, à la manière d'une molécule d'un gaz confiné dans une enceinte. Ecrivons 1 ou 2 suivant que la boule rebondit sur une bande horizontale ou verticale. Pour une direction donnée de lancement, les rebonds successifs forme un mot infini sur l'alphabet {1,2}. Toute suite de "1" et de "2", et en particulier la suite de Kolakoski, est ainsi susceptible de coder l'angle d'une direction de lancer.
L'intérêt de tels "billard mathématiques" et des mots du type Kolakoski, vient de l'étude des nombres : à tout nombre réel correspond une suite illimitée de décimales (on néglige la virgule), ou plus généralement, dans un sytème de numération à base k, un mot infini sur un alphabet de k symboles (les "chiffres" du système de numération).
La problématique générale consiste à trouver des relations entre la manière dont un nombre est défini (par exemple comme solution d'une équation) et son écriture dans une base donnée. On sait par exemple qu'aux nombres rationnels (les fractions) correspondent des mots périodiques alors que pour d'autres nombres, les chiffres successifs semblent distribués "au hasard". L'exemple le plus fameux est sans doute celui de l'écriture décimale du nombre p, qui, apparemment, se comporte de manière aléatoire (on conjecture en particulier que chacun des 10 chiffres y apparaît une infinité de fois).
Les préoccupations modernes sur le hasard, le déterminisme et le concept de chaos avivent l'intérêt des mathématiciens pour ces questions : la suite apparement aléatoire et imprévisible des décimales d'un nombre peut en fait cacher une loi qui engendre "automatiquement" les termes successifs.
Ce domaine de recherche est un carrefour entre Théorie des Nombres, Combinatoire (qui examine les manières dont des structures s'organisent à partir de composants élémentaires), Théorie des Système Dynamiques (qui vise à comprendre le devenir d'un phénomène soumis à une loi d'évolution connue), Théorie des Automates (qui étudie notamment des procédés simples de fabrication pour des mots infinis non périodiques), et Théorie des Probabilités (il s'agit plus exactement de "Théorie Ergodique", qui s'intéresse au caractère aléatoire de la distribution des symboles dans des mots infinis, notamment ceux des "billards mathématiques").
|
|
|
|
|
