Martin Delacourt
LORIA, Vandœuvre-lès-Nancy
https://www.univ-orleans.fr/lifo/Members/delacourt/
Date(s) : 26/04/2016 iCal
11 h 00 min - 12 h 00 min
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 dans cette étude 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.
Calculating in a reversible unidirectional cellular automaton: towards the undecidability of periodicity?
We are interested in the parallel between 2 problems on distinct models of automata. On the one hand, Mealy’s automata (complete letter-to-letter transducers) which produce semi-groups generated by transformations on infinite words associated with states. In 2013, Gillibert showed that the problem of the finiteness of these semi-groups was undecidable. On the other hand, the question is open in the case where the Mealy automaton produces a group.
On the other hand, unidirectional cellular automata for which the question of the decidability of periodicity is open. We can show the equivalence of these problems.
We will make a step in this study by showing that it is possible to simulate Turing calculus in a reversible unidirectional cellular automaton, thus making prediction problems undecidable.
https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
http://www.loria.fr/~mdelacou/
Catégories