Courbes d'accumulations des machines à signaux

Cette thèse s'inscrit dans l'étude d'un modèle de calcul géométrique : les machines à signaux. Nous y montrons comment tracer des graphes de fonctions à l'aide d'arbres unaire-binaires. Dans le monde des automates cellulaires, il est souvent question de particules ou signaux : des structures périodiques dans le temps et l'espace, autrement dit des structures qui se déplacent à vitesse constante. Lorsque plusieurs signaux se rencontrent, une collision a lieu, et les signaux entrant peuvent continuer, disparaître ou laisser place à d'autres signaux, en fonctions des règles de l'automate cellulaire. Les machines à signaux sont un modèle de calcul qui reprend ces signaux comme briques de base. Visualisées dans un diagramme espace-temps, l'espace en axe horizontal et le temps vertical s'écoulant vers le haut, ce modèle revient à calculer par le dessin de segments et demi-droites colorés. On trace, de bas en haut, des segments jusqu'à ce que deux ou plus s'intersectent, et l'on démarre alors de nouveau segments, en fonctions de règles prédéfinies. Par rapport aux automates cellulaires, les machines à signaux permettent l'émergence d'un nouveau phénomène : la densité des signaux peut être arbitrairement grande et même infinie, y compris en partant d'une configuration initiale de densité finie. De tels points du diagramme espace-temps, des points au voisinage desquels se trouvent une infinité de signaux, sont appelés points d'accumulation. Ce nouveau phénomène permet de définir de nouveau problèmes, géométriquement. Par exemple : quels sont les points d'accumulations isolés possibles en utilisant des positions initiales et des vitesses rationnelles ? Peut-on faire en sorte que l'ensemble des points d'accumulation forment un segment ? un ensemble de Cantor ? Dans cette thèse, nous nous attelons à caractériser des graphes de fonctions qu'il est possible de dessiner par un ensemble d'accumulation. Elle s'inscrit dans l'exploration de la puissance de calcul des machines à signaux, qui s'inscrit plus généralement dans l'étude de la puissance de calcul de modèles non standards. Nous y montrons que les fonctions d'un segment compact de la droite réelle dont le graphe coïncide avec l'ensemble d'accumulation d'une machine à signaux sont exactement les fonctions continues. Nous montrons plus généralement comment les machines à signaux peuvent dessiner n'importe quel fonction semi-continue inférieurement. Nous étudions aussi la question sous des contraintes de calculabilité, avec le résultat suivant : si un diagramme de machine à signaux calculable coïncide avec le graphe d'un fonction suffisamment lipschitzienne, cette fonction est limite calculable d'une suite croissante de fonctions en escalier rationnelles.