Cellular automata and self-organisation phenomena

Univ Rouen Normandie, CNRS, Normandie Univ, LMRS UMR 6085, F-76000 Rouen, France

Abstract

Cellular automata are dynamical systems for which time and space are discrete. They are used to model the evolution of a set of components, the cells, that interact locally with each other: over time, each cell updates its state according to what it perceives in its neighbourhood. Some cellular automata exhibit a self-organisation behaviour: from an initial disordered state, successive updates of the cells by the local rule lead to the emergence of a macroscopic structure. Conversely, given a desired global behaviour, we can ask ourselves which local rules allow to achieve this collective behavior, in a decentralised way. In this article, we will address several such inverse problems (synchronisation, density classification, self-correction of tilings), and study the influence that the introduction of randomness can have on the dynamics.

Résumé

Les automates cellulaires sont des systèmes dynamiques pour lesquels le temps et l’espace sont discrets. Ils permettent de modéliser l’évolution d’un ensemble de composantes, les cellules, interagissant entre elles de manière locale : au cours du temps, chacune actualise son état en fonction de ce qu’elle perçoit dans son voisinage. Certains automates cellulaires exhibent des comportements d’auto-organisation : à partir d’un état initial désordonné, les mises à jour successives des cellules par la règle locale conduisent à l’apparition d’une structure macroscopique. A l’inverse, si l’on souhaite parvenir à un certain comportement global, on peut se demander quelles règles locales permettent de l’atteindre de manière décentralisée. Dans cet article, nous présenterons plusieurs problèmes inverses de ce type (synchronisation, classification de la densité, auto-correction de pavages), en étudiant l’influence que peut avoir l’introduction d’aléa dans les dynamiques.