Gaétan Richard (GREYC, Caen)

Les automates de sables 1D sont un modèle dynamique introduit comme une généralisation des tas de sables. Il s’agit d’un système unidimensionnel synchrone, uniforme et local qui se base sur des valeurs arbitrairement grandes. Du point de vue dynamique, ce système peut être vu comme un intermédiaire entre les automates cellulaires de dimension 1 et le dimension

  1. Sur ce dernier point, une piste particulièrement interessante est l’étude de la propriété de surjectivité car elle est décidable dans le premier cas et non dans le second.

Cet exposé s’intéressera particulièrement à la façon d’introduire du calcul dans un système très contraint. Nous montrerons l’indécidabilité de la surjectivité des automates de sables 1D en simulant des machines de Minski (machines à deux compteurs).

Last modified: Mon Nov 24 10:54:03 CET 2014