Articles by Benjamin Hellouin
Compléter des colorations partielles de hom shifts
summary: On étudie les shifts ou espaces de pavages de type fini : des colorations de la grille régulière infinie qui évitent un ensemble fini de motifs interdits. Il s'agit d'un modèle étudié en particulier comme source apparemment infinie de problèmes indécidables.
Les hom shifts sont une restriction du ...
Automates cellulaires surjectifs et mesures de probabilité
summary: Les automates cellulaires sont un modèle de calcul simple consistant en une coloration d'un graphe infini régulier (typiquement, une ligne infinie) sur lequel on itère une transformation locale uniforme. Ce modèle est capable de calcul universel dans un certain sens, y compris quand la configuration initiale est choisie ...
Calculer le taux de croissance du nombre de motifs d'un pavage
Résumé :
Les pavages correspondent à des coloriages d'une grille (Z ou Z^d) qui obéissent à des contraintes locales. Compter ou énumérer les coloriages admissibles de sous-ensembles finis est une question combinatoire naturelle, et le taux de croissance de ce nombre correspond à une notion d'entropie qui apparait ...
Universal computation and asymptotic behaviour in symbolic dynamics.
Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...