Suites et ensembles automatiques : autour d'un théorème de Cobham

par Boris Adamczewski

mardi 18 oct. 2016, 10:30 → 12:30 Europe/Paris

salle Fokko du Cloux (ICJ, UCBL - La Doua, Bât. Braconnier)

Le groupe de travail du projet ANT reprend cette année avec un cycle d'exposés autour d'un joli théorème dû à Cobham à la fin des années soixante. Ce résultat formalise, à l'aide de la théorie des automates finis, l'idée naïve et intuitive suivante: s'il est aisé de reconnaître qu'un entier écrit en base 2 est une puissance de 2, cela est bien moins évident lorsque cet entier est écrit en base 3. Tout le sel du théorème de Cobham vient du fait qu'il a donné lieu à des travaux d'origines très diverses (théorie des modèles, pavages, fractales, arithmétique, équations aux différences et analyse...), notamment récemment. Dans ce premier exposé, qui ne nécessitera aucun pré-requis, j'expliquerai ce que sont les suites et les ensembles automatiques, je présenterai le théorème de Cobham et certaines de ses généralisations, ainsi que son lien avec les équations mahlériennes.