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

Carte non disponible

Date/heure
Date(s) - 26/04/2016
11 h 00 min - 12 h 00 min

Catégories


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.

http://www.loria.fr/~mdelacou/

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange