Comment des interactions simples entre des entités extrêmement simples peuvent-elles engendrer des comportements complexes, jusqu'à des mécanismes auto-reproducteurs ?
Les automates cellulaires sont des modèles abstraits simulant le fonctionnement des ordinateurs. Par là, ils sont à rapprocher des machines de Turing. Si cet aspect est important, ce n'est pas celui sur lequel nous allons nous concentrer dans le cadre de ce cours. C'est sur leurs capacités de modéliser des systèmes complexes que nous allons nous focaliser. Ces derniers sont constitués d’un grand nombre d’entités en interaction qui évoluent au cours du temps. Le comportement des entités dépend à la fois de l'environnement et des autres entités qu’elles peuvent observer localement autour d’elles. On peut citer différents exemples comme le trafic routier, les nuées d’oiseaux, occupation de nids d’abeille, tissus cellulaires ...
À partir de règles simples les automates cellulaires permettent de générer des évolutions extrêmement riches.
Les automates cellulaires ont été proposé dans les années 1950 par John von Neumann suite à une suggestion de son ami le mathématicien Stanislaw Ulam. Alors qu'il s'interrogeait sur comment concevoir une machine capable de s'auto-reproduire, Ulam l'orienta vers une question moins vaste : quelle organisation logique est suffisante pour un automate pour être capable de s'autoreproduire ?
Von Neumann fait alors le choix de considérer le problème dans un espace mathématique simple, métaphore du monde réel. L'espace est une grille régulière composée de cellules qui ont un état choisi dans un ensemble fini d'états possibles. L'évolution se fait à chaque pas de temps en fonction de règles locales.
Cette vision initiera tout un développement encore très actif autour des automates cellulaires, c'est ce que nous allons exposer partiellement dans la suite.
Description
Les automates cellulaires sont des machines à états finis évoluant sur une grille infinie, le plus souvent, et de dimension n. Les dimensions habituelles sont généralement 1 ou 2. La grille définit un espace discret et un voisinage pour chacune des cases de la grille. Cette grille peut être régulière ou non et les cases peuvent prendre différentes formes (rectangulaire, hexagonale ....).
On associe à chaque case de la grille une cellule, cette dernière va alors avoir un état, ce dernier est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons que le premier cas.