Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 25 Novembre 2014

Aux limites de l'indécidabilité: le problème de la surjectivité des automates de sables

par 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 2. 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).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr