Institut de Recherche sur l'Enseignement des Mathématiques de Paris

Nous proposons quelques réflexions autour de la question de savoir si une suite (de nombres, de symboles, etc.) est plus ou moins «compliquée».
Une première remarque est qu'une suite «au hasard» (c'est- à-dire presque toute suite) semble pouvoir être légitimement qualifiée de compliquée, alors qu'une suite périodique (et de petite période ?) semble mériter le qualificatif de «simple».
Nous aborderons différents thèmes : la complexité de Kolmogorov et la compressibilité, la complexité algorithmique, la complexité par blocs... Puis nous nous concentrerons sur un type particulier de suites algorithmiques, les suites engendrées par automate fini et par morphisme de monoïde, ce qui nous permettra une digression sur la question : transcendance de réels et complexité de leur représentation décimale.
Dans une dernière partie nous décrirons une manière d'appréhender les «fluctuations» d'une suite, ce qui est une autre (?) approche de la complication d'une suite.