Dubacq
Le 10 Janvier 2002 à 14h30
au LRI,
Salle 101
(LRI))
Signaux pour automates cellulaires en dimension 2 ou plus
Résumé/Abstract :
Les automates cellulaires, systèmes dynamiques très simples,
utilisent de façon informelle la notion de signal. Après avoir
vu comment définir cette notion, nous verrons qu'il existe une gamme
de signaux simples et qu'on ne peut pourtant pas construire lorsqu'on regarde
près du ``temps réel''. De façon assez inattendue, nous
montrerons que ce résultat connu en dimension 1 reste vrai quelle que
soit la dimension, puis nous montrerons comment on peut malgré cela
réduire le nombre d'états nécessaires pour certaines
constructions en passant en dimension supérieure.
(les transparents de l'exposé sont accessibles
ici)
Signals for cellular automata in dimension 2 or higher
We investigate how increasing the dimension of the array can help to
draw signals on cellular automata. We show the existence of a gap of
constructible signals in any dimension. We exhibit two cellular
automata in dimension 2 to show that increasing the dimension allows
to reduce the number of states required for some constructions.