Sciences et Médecine
~~~~~~
Suites infinies, complexité et géométrie
TAPSOBA T.
.
RÉSUMÉ
Par une démarche trèssimple,nous montrons que la définition «classique» de la fonction de complexité ne permet pas vraiment de
décrire comment une suite est ...«complexe».
Mots clés:Suites infinies, suites ultimement périodiques, substitutions, complexité.
ABSTRACT
Using a simple approach we show that the «classical» definition of complexity function does not allow ta describe how a sequence is
...«complex».
Key-words: Infinite sequences, ultimately periodicsequences, substitutions, complexity.
1. INTRODUCTION
- l'itération; l'itérée du langage L, notée L*, est l'union de
1.1 Mots
toutes les puissances de L.
Soit A un ensemble fini appelé alphabet dont les
éléments sont appelés lettres et soit n un entier strictement
1. 4 Remarque
positif. Un mot u de longueur n (on note alors lui = n) sur
Le lecteur intéressé pourra se référer à [14] pour plus de
l'alphabet A est.par définition unn-uplet (u, ... , un) de lettres
détails sur toutes les notions ci-dessus.
de A. L'ensemble des mots sur l'alphabet A est noté A*.
Par convention, on appelle mot vide le mot de longueur 0
If. SUITES INFINIES
(souvent noté e).
2.1 Suites ultimement périodiques
Une suite (x)nvIN est dite ultimement périodique s'il
Sur A* on définit une importante opération appelée
existe un entier non nul r et un entier nO tels que xn+t=xnpour
concaténation qui associe à deux mots u et v de A*, un mot
tout nan"
w noté uv défini comme suit:
~ Si u = e,alors uv = v,
2.2 Une approche
Siv = e,alors uv-eu,
Lançons «indéfiniment»
une pièce de monnaie et
>
-
- Si u = (u, ... , un) et v = (v" ... , v ) , alors Uv = (u, ... , un'v"
regardons la suite:
k
... , v ) ·
PFFFPPFFPPFPFF ... des «pile» et «face» obtenue. Cette
k
On confère ainsi une structure de monoïde à A* où le
suite étant construite au hasard, les lois statistiques seront
mot vide est l'élément neutre. Comme la concaténation
observées; ainsi la fréquence d'apparition d'un mot donné,
est associative, on se passe de parenthèses pour écrire tout
par exemple PF, sera très proche de sa probabilité (dans
simplement le mot uvw à la place de u(vw) ou (uvlw,
notre cas) et cela sera certainement vrai pour tout mot.
1.2 Facteurs
Plus généralement, une suite sur un alphabet de deux
Soit un mot de A*. Le mot v de A* est dit factaur de u,
lettres est dite normale si pour tout entier 'strictement
s'il existe deux mots w et w' de A* (éventuellement vide(s))
positif p.tour.vvit de longueur p apparaît dans la suite avec
tels que u=wvw: Avec cette notation, si w (resp. w') est le
la fréquence _1_ .
>
,Ji
mot vide, v est dit préfixe (resp. suffixe) de u. On désigne
respectivement par Fact(u), Préf(u),Suf(u) les ensembles des
Il existe des algorithmes pour construire des suites
facteurs, préfixes et suffixes de u.
normales. La plus connue de ces suites est celle de
>
Champernowne: on écrit la suite des entiers naturels 0, 1,2, .
1.3 Langages
en base deux, ce quidonne la suite 0110111001011101 ll .
Un ensemble de mots sur un alphabet donné est
appelé langage sur cet alphabet. Trois groupes principaux
Si les procédés pour construire des suites infinies sont
d'opérations peuvent être définis sur les langages:
nombreux, l'auto-référence est certainement la méthode
- les opérations booléennes ; il s'agit là des opérations
la plus simple pour obtenir des suites non ultimement
ordinaires de la théorie des ensembles: union, intersection,
périodiques.
complémentation.
-le produit et les puissances; si Let M sont deux langages sur
Eco/eSupérieure d'Informatique
l'alphabet A,le produit L.M de ces langages est l'ensembles
Univ. po/ytech. de Bobo·Diou/asso
des mots w vérifiant w=uv où uvL et vvM. La n-ième
01 BP 1091 Bobo-Diou/asso 01
puissance de L, notée Ln est définie par récurrence par
Burkina Faso
Té/.:(+226)70260514
LO=e, Ln+'=L.Ln=Ln.L.
E-Mail: theo_tapsoba@univ-ouaga.bf
94
Rev. CAMES - Série A, Vol. 06,2008
SCiences et Médecine
2.3 Suites se référant à elles-mêmes
III. Complexité
Une suite {xn)nvIN est dite Markovienne si xn+, ne dépend
3.1 La fonction de complexité
que de x . Par ce que nous appelons l'auto-référence nous
La suite de Fibonacci est peut-être l'exemple le plus
obtenons des suites qui ne sont pas Markoviennes, bien que
«simple» de suite substitutive. Il est donc permis de penser
n'étant pas très éloignées. Une suite se référant à elle-même
que la notion de complexité prendra ce fait en compte...En
est une suite telle que lorsque les n premiers termes sont
effet, la proposition précédente semble indiquer d'une part
écrits,on sait écrire le {n+ 1Hème terme en ne regardant que
que la fonction P{n) joue un rôle dans la description de la
les m premiers termes, où msn, On essaye donc de créer
complexité et d'autre par que cette fonction peut facilement
un programme permettant d'écrire ses termes successifs. Ce
être calculée lorsque des propriétés géométriques sont
programme peut lui aussi être écrit comme une suite sur le
connues.
même alphabet. Plus cette dernière suite est courte, moins
la suite donnée au départ est complexe.
D'où la définition suivante de la fonction de complexité
(voir par exemple [2]) : soit x une suite infinie et L=Fact{x) le
Malheureusement cette
définition
classique
de
la
langage associé à x. La fonction de complexité de x, notée
complexité d'une suite due à Kolmogorov, Chaitin et
P{x, n) est le nombre de facteurs distincts de longueur n de
Solomonoff [8] n'est pas effective; en effet, pour une suite
L.
donnée, il n'existe pas toujours un algorithme permettant
d'écrire le plus petit programme nécessaire pour la générer.
3.2 Complexité et prédiction
Soit x une suite sur un alphabet A et P{x, n) sacomplexité.
Dans ce qui va suivre, nous nous restreindrons à une
Supposons que l'on sache qu'un mot u de longueur n
auto-référence particulière nommée substitution,on obtient
apparaît à un certain endroit dans x, c'est-à-dire qu'il existe
alors des suites infinies appelées suites substitutives ([13],
k tel que x{k)x{k+ 1)... x{k+n-1 )=u. Peut-on prédire alors la
[9], [5], ...).
valeur de x{k+n)?
2.4 Suites substitutives
Posons À{u)=Card(avA!uavFact{x)}. Si À{u)=l, u se
Soit A= (0, l} et f la fonction de A dans A* définie par
prolonge de manière unique (mettons ua) et on peut
f (0)=01, et f (1 )=0. Nous étendons cette définition aux mots
prédire avec exactitude que x{k+n)=a. Il y a donc deux cas
et aux suites par f (xy)=f{x) f(y).
extrêmes:
(i) « u, mot de longueur n. À{u)= 1; (parfaite prédiction).
En commençant du mot 0, on obtient successivement
(ii) « u, mot de longueur n, À{u)= Card{A) ; (prédiction
01,010,01001,01001010, .... 11 est facile de voir que si u{n)
impossible).
est le mot obtenu à la n-ième étape, u{n) est préfixe de
u(n+ 1). On construit ainsi une suite substitutive {notée Fib
Notons que pour lul=n, la somme sur u des À{u) vaut
et appelée suite de Fibonacci ([4], [10], [7], [12], ...) vérifiant
P{n+ 1), et donc que la somme des (À{u)-l )=P{n+ 1)-P{n)
Fib=Ol 00101 001001...et qui débute par u{n) pour tout n. On
(notée s{n)). Dans le cas (i), s{n)=O et donc P{n+1)=P{n) ;
a évidemment Fib=f (Fib) et c'est la seule suite ayant cette
dans le cas (ii), s{n)=P(n)(Card{A)-l) si bien que P{n+1)=P{n)
propriété.
Card{A).
.J5 -1
Posons a
soit X = [0, 1[, XO = [0, œ] et
Si (ii) est vraie pour tout n, on obtient P{n)={Card{A))n.
2
Si ri) est vraie pour tout n, on montre facilement que pour
X, = [a, 1[.Soit T: ~ X tel que T{x)=x+ t-œ si xvX et T{x)=x-a
o
Ivl=n+ l. la somme des (À{u)-l )=O=s{n+ 1) et une récurrence
si xvX,. Désignons par X{x) l'élément de (0, 1} tel que xV\\(Xr
donne P{m)=P{n) pour tout mz n.1I est clair (Voir néanmoins
La suite (X{T"{x)))nvIN est appelée l'itinéraire de x et est notée
[6] par exemple) que pour que l'on ait cette dernière
it{x). On a alors (voir par exemple [11]) :
égalité, il faut et il suffit que x soit ultimement périodique.
On en conclut de prime abord que la croissance de la suite
Proposition
2.7' Les
conditions
suivantes
sont
(P{n+1)-P{n))nvIN mesure dans un certain sens la possibilité
équivalentes:
de prédire la suite x.
(i) Pour tout x de X, l'orbite de x, c'est-à-dire la suite
(T"{x))nvIN est dense dans X.
IV. Complexité et Géométrie
(ii) Pour tout x de X, le langage Fact{it{x)) ne dépend pas
Nous avons dit plus haut que si pour une suite x, la
de x. on le notera L.
fonction P(n) n'est pas strictement croissante alors x est
(iii) Le nombre P{n) des éléments de L de longueur n est
ultimement périodique.Ainsi,avoir une suite non ultimement
P(n)=n+ 1.
périodique suppose s{n)~l pour tout n. La complexité la plus
(iv) La suite Fib est l'itinéraire du point a 2•
faible envisageable est donc P{n)=n+ 1. Rappelons que (on
peut le prouver par des arguments géométriques) la suite
Remarque 2.7 (i), (ii) et (iii) restent vraies pour tout
de Fibonacci vérifie cette propriété et on a (voir par exemple
irrationnel a de {O, 7(.
[3]) :
Rev. CAMES- Série A, Vol. 06,2008
95
Sciences et Médecine
Proposition 4. 1 Si une suite x vérifie P(x)=n+1 alors elle
6- HEDLUND G.A.et MORSE M., Symbolic dynamics,Amer.
.~st l'itinéraire d'un échange entre deux intervalles.
J. Math. 60 (1938),815-866.
Il vient alors cette question: Si pour une suite donnée,
7- KASA Z., Computing the d-cornplexty of words by
P(n) a une expression simple, a t-elle une interprétation
Fibonacci-Iike sequences, Studia Univ.. Babes-Bolyai.
géométrique? De nos jours.la question précédente n'est pas
Math.35 (1990),49-53.
résolue dans sa généralité. Il est indispensable d'ajouter des
conditions de type combinatoire (voir par exemple [1]) si on
8- LI M. et VIANTANYI P., Kolmogorov complexity and its
désire avoir des caractérisations nécessaireset suffisantes. Il
applications, in J. Van Leeuwen éditeur, Handbook of
apparaît donc que la fonction P(n) seule ne suffit pas pour
Theoretical Computer Science, Volume A : Algorithms
vraiment décrire la complexité d'une suite...
and complexity, MIT Press (1990),187-254.
R~FÉRENCES
9- MOULINE J., Contribution à l'étude de la complexité
des suites substitutives, Thèse de Doctorat, Université de
1- ARNOUX P. et RAUZY G., Représentation qéométrlque
Provence (1989).
de suites de complexité 2 + , Bull. Soc. Math. de France
n 1
119 (1991),199-215.
1O-PANSIOT J.-J., Mots de Fibonacci et morphismes itérés,
Lecture Notes in Computer Science 172 (1984).380-389.
2- COBHAM A., Uniform tag sequences, Math. Syst.Theo. 6
(1972) 164-192.
11-QUEFFELEC
M.,· Substitution
dynamical
systems,
Spectral analysis, Lecture Note in Mathematics 1294
3- COVEN E. et HEDLUND G.A., Hedlund, Sequences with
(1987),Pringer-Verlag Berlin.
minimal block growth, Math. Systems Theory 7 (1973),
138-153.
12- S~ÉBOLD P., Fibonacci morphisms and Sturmians words,
Theoret. Comput. Sei. 88 (1991) 365-384.
4- De LUCAS A., A combinatorial property of the Fibonacci
word, Information processing. Letters 12 n° 4 (1981),193-
13- TAPSOBA T., Complexité de suites automatiques, Thèse
195.
de 3ème cycle, Université d'Aix-Marseille Il (1987).
5- DURAND F.,Contribution à l'étude des suites et systèmes
14- TAPSOBA T., Contribution
à
l'étude
des
suites
dynamiques substitutifs, Thèse de Doctorat, Université
automatiques, Thèse de Doctorat d'Etat, Université de
d'Aix-Marseille" (1996).
Ouagadougou (1999).
96
Rev. CAMES - Série A, Vol. 06,2008