BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:7831@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20160426T110000
DTEND;TZID=Europe/Paris:20160426T120000
DTSTAMP:20241120T204846Z
URL:https://www.i2m.univ-amu.fr/evenements/calculer-dans-un-automate-cellu
 laire-unidirectionnel-reversible-vers-l-indecidabilite-de-la-periodicite/
SUMMARY:Martin Delacourt (LORIA\, Vandœuvre-lès-Nancy): Calculer dans un 
 automate cellulaire unidirectionnel réversible : vers l'indécidabilité 
 de la périodicité?
DESCRIPTION:Martin Delacourt: 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-gr
 oupes engendrés par les transformations sur les mots infinis associées a
 ux états. En 2013\, Gillibert a montré que le problème de la finitude d
 e ces semi-groupes était indécidable. En revanche la question est ouvert
 e dans le cas où l'automate de Mealy produit un groupe.\nD'autre part\, l
 es automates cellulaires unidirectionnels pour lesquels la question de la 
 décidabilité de la périodicité est ouverte. On peut montrer l'équival
 ence de ces problèmes.\nOn fera un pas dans cette étude en montrant qu'i
 l est possible de simuler du calcul Turing dans un automate cellulaire uni
 directionnel réversible\, rendant ainsi des problèmes de prédiction ind
 écidables.\nCalculating in a reversible unidirectional cellular automaton
 : towards the undecidability of periodicity? \nWe are interested in the pa
 rallel between 2 problems on distinct models of automata. On the one hand\
 , Mealy's automata (complete letter-to-letter transducers) which produce s
 emi-groups generated by transformations on infinite words associated with 
 states. In 2013\, Gillibert showed that the problem of the finiteness of t
 hese semi-groups was undecidable. On the other hand\, the question is open
  in the case where the Mealy automaton produces a group.\nOn the other han
 d\, unidirectional cellular automata for which the question of the decidab
 ility of periodicity is open. We can show the equivalence of these problem
 s.\nWe will make a step in this study by showing that it is possible to si
 mulate Turing calculus in a reversible unidirectional cellular automaton\,
  thus making prediction problems undecidable.\nhttps://hal-univ-orleans.ar
 chives-ouvertes.fr/hal-01436460\n\nhttp://www.loria.fr/~mdelacou/
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Martin_Delacourt.jpg
CATEGORIES:Séminaire,Ernest
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20160327T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR