Olivier Carton : la normalité de l’aléatoire

Si le modèle des machines de Turing est central en informatique, il n’est pas le seul à retenir l’attention des chercheurs. Olivier Carton, professeur à l’Université Paris Cité et membre de l’IRIF, lui préfère d’autres modèles de calcul. « Je m’intéresse aux automates à états finis, précise Olivier Carton. Ils présentent une puissance de calcul plus faible que les machines de Turing, mais ils fonctionnent et se manipulent également mieux d’un point de vue algorithmique. ».

Les travaux d’Olivier Carton se concentrent plus particulièrement sur les transducteurs, c’est-à-dire les automates à états finis sur lesquels il y a une entrée et une sortie. Ce modèle de calcul relativement simple est économe en ressource. Ses applications concernent surtout les traitements des flux d’informations, comme ceux du streaming. Olivier Carton penche cependant surtout du côté de la recherche fondamentale.

Il collabore ainsi assidûment avec Verónica Becher, professeure à l’Université de Buenos Aires, ville où il se rend régulièrement. « Verónica Becher ne travaillait au départ pas sur les automates, mais nous nous sommes retrouvés sur l’étude de la normalité, précise Olivier Carton. Introduite par Émile Borel en 1908, cette notion concerne les suites de chiffres aléatoires. Elles sont dites normales si chaque chiffre apparaît autant de fois que les autres, ce qui est naturellement attendu, mais ce doit aussi être le cas pour des blocs de plusieurs chiffres consécutifs. » Or il existe de nombreuses situations où il n’est pas encore possible de prouver que, par exemple, tous les chiffres apparaissent bien une infinité de fois dans le nombre √2, écrit en base 10. De plus, ces travaux ne se limitent pas au calcul en base 10, ce qui les complique encore un peu plus.

« La notion de normalité est importante pour l’étude des automates, car il existe des liens entre la normalité d’une suite de chiffres et la capacité d’un automate à états finis à la compresser et à la récupérer », poursuit Olivier Carton. L’idée étant, à l’origine, que les suites de chiffres normales ne peuvent pas être compressées par un transducteur. Olivier Carton a montré que cette notion était robuste, c’est-à-dire qu’elle variait peu en fonction du type d’automate utilisé, en dehors des machines de Turing. Il a ainsi aidé à mieux délimiter les frontières des ensembles qu’il est possible ou non de compresser.

Olivier Carton travaille également sur l’indépendance de la normalité, c’est-à-dire identifier les paramètres dont elle ne dépend pas. « Nous avons pour cela ajouté des contraintes à des suites normales, par exemple obliger que le chiffre à la position n soit le même qu’à la position 2n, explique Olivier Carton. C’est complètement inattendu, mais cela ne change pas la normalité. »

Ces nombreuses contributions dans le domaine lui valent d’être nommé membre senior de l’Institut universitaire de France (IUF), à une chaire fondamentale. « Cela va me permettre d’inviter plus de chercheurs dans mon laboratoire et de développer mes collaborations, y compris en Argentine, se réjouit Olivier Carton. Car ce que j’aime dans la recherche, c’est réfléchir avec quelqu’un devant un tableau noir. »