Calculer dans un automate cellulaire unidirectionnel réversible : vers l’indécidabilité de la périodicité ?

On s’intéresse au parallèle entre 2 problèmes sur des modèles distincts d’automates.

D’une part, les automates de Mealy (transducteurs lettre à lettre complets) qui produisent des semi-groupes engendrés par les transformations sur les mots infinis associées aux états. En 2013, Gillibert a montré que le problème de la finitude de ces semi-groupes était indécidable. En revanche la question est ouverte dans le cas où l’automate de Mealy produit un groupe.

D’autre part, les automates cellulaires unidirectionnels pour lesquels la question de la décidabilité de la périodicité est ouverte.

On peut montrer l’équivalence de ces problèmes. On fera un pas vers une preuve d’indécidabilité en montrant qu’il est possible de simuler du calcul Turing dans un automate cellulaire unidirectionnel réversible, rendant ainsi des problèmes de prédiction indécidables ainsi que la question de la périodicité partant d’une configuration donnée finie.