Universality in Freezing Cellular Automata
Florent Becker  1@  , Diego Maldonado  1@  , Nicolas Ollinger  1@  , Guillaume Theyssier  2@  
1 : Laboratoire d'Informatique Fondamentale d'Orléans  (LIFO)  -  Site web
INSA Centre Val de Loire, Université d'Orléans : EA4022
Bâtiment IIIA Rue Léonard de Vinci B.P. 6759 F-45067 ORLEANS Cedex 2 -  France
2 : Institut de Mathématiques de Marseille  (I2M)  -  Site web
Aix Marseille Université : UMR7373, Ecole Centrale de Marseille : UMR7373, Centre National de la Recherche Scientifique : UMR7373
Centre de Mathématiques et Informatique (CMI)Technopôle Château-Gombert39, rue Frédéric Joliot Curie13453 Marseille Cedex 13 -  France

Cellular Automata have been used since their introduction as a discrete tool of modelization. In many of the physical processes one may modelize thus (such as bootstrap percolation, forest fire or epidemic propagation models, life without death, etc), each local change is irreversible. The class of freezing Cellular Automata (FCA) captures this feature. In a freezing cellular automaton the states are ordered and the cells can only decrease their state according to this "freezing-order".

We investigate the dynamics of such systems through the questions of simulation and universality in this class: is there a Freezing Cellular Automaton (FCA) that is able to simulate any Freezing Cellular Automata, i.e. an intrinsically universal FCA? We show that the answer to that question is sensitive to both the number of changes cells are allowed to make, and geometric features of the space. In dimension 1, there is no universal FCA. In dimension 2, if either the number of changes is at least 2, or the neighborhood is Moore, then there are universal FCA. On the other hand, there is no universal FCA with one change and Von Neumann neighborhood.


Personnes connectées : 1