Résultats autour de la conjecture d'Hartmanis et Stearns

Abstract

S'il est connu que les rationnels ont une représentation en base b ultimement périodique, et ce pour tout entier b ≥ 2, que peut-on dire sur la représentation en base b des nombres irrationnels, et en particulier des irrationnels algébriques ? La conjecture de Borel prédit notamment que tout irrationnel algébrique est normal dans toute base b ≥ 2. Afin d’étudier cette question, nous adoptons le cadre de la théorie de la complexité introduit par Hartmanis et Stearns en 1965 à l’aide des machines de Turing. Leur approche consiste à mesurer le temps nécessaire à une machine de Turing pour produire les chiffres du développement d’un nombre réel. Ils posent alors la question suivante : existe-t-il des irrationnels algébriques dont le développement en base b peut être généré en temps linéaire ? La conjecture de Hartmanis et Stearns, toujours ouverte aujourd’hui, postule que la réponse est négative. Dans ce mémoire, nous étudions plusieurs restrictions de cette question en considérant des modèles de calcul plus faibles que les machines de Turing, et montrons que ces modèles ne permettent pas de produire le développement en base b d’un irrationnel algébrique.