Automates Cellulaires, Automates à Partitions et Tas de Sable

(un peu prétencieux non?)
« Pour ce qu'alors, je désirais vaquer seulement à la recherche de la vérité, je pensai qu'il fallait (...) que je rejetasse, comme absolument faux, tout ce en quoi je pourrais imaginer le moindre doute, afin de voir s'il ne resterait point, après cela quelques chose en ma créance, qui fût indubitable. »

Descartes, Discours de la Méthode, 1637.

Si l'impression est indispensable, veuillez ne l'imprimer qu'en
- recto simple sur du brouillon (français 120 pp, 320K)
ou
- recto-verso

Résumé

Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires.

Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le ``Billiard ball model'' de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension.

Dans un espace linéaire, ``Tas de sable'' et ``Chip firing game'' sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en oeuvre.

Mots-Clés

Automates Cellulaires, Automates à Partitions, Réversibilité, Simulation, Tas de Sable Linéaires, Chip Firing Game et Billiard Ball Model.

Abstract

This thesis deals with two topics. The first is the reversible simulation of cellular automata. The second is the evolution in linear space of the Sand Pile Model and of the Firing Chip Game.

We make various simulations that link cellular automata and partitioning cellular automata. In particular, we prove a 1990 conjecture that reversible cellular automata can be simulated by reversible partitioning automata. We show that the Billiard Ball Model of Toffoli and Margolus is able to simulate any reversible partitioning automaton of dimension two. It follows that there are reversible cellular automata able to simulate any reversible cellular automaton of the same dimension.

In linear space, the Sand Pile Model and the Chip Firing Game are equivalent. We especially study the case of grain dripping. Patterns delimited by signals appear. We study their interactions and make asymptotic approximations. Our methods and results are applied to other cases. Over the cases studied, massive parallelism is achieved: sequential and parallel times differ by a factor corresponding to the number of active piles.

Key-Words

Cellular Automata, Partitioning Automata, Reversibility, Simulation, Sand Pile Model, Chip Firing Game and Billiard Ball Model.

Resumen

Esta tesis toca dos temas : en primer lugar, se interesa por la simulación de los autómatas celulares reversibles, y en segundo lugar, por la dinámica de los modelos lineales de Pilas de arena y de Tiro de fichas.

Construimos diversas simulaciones que vinculan los autómatas celulares y los autómatas con particiones. En particular, se desmuestra una conjeatura de 1990 sobre la simulación de automatas celulares reversibles. Mediante construciones sucecivas, mostramos que el modelo de la bola de billar de Toffoli y Margolus es capaz de simular todos los autómates con particiones reversibles de dimensión dos. Con estos resultados, establecemos que existen autómates celulares reversibles capaces de simular cualquier autómata celular reversible de la misma dimensión.

En un espacio lineal, Pilas de arena y Tiro de fichas son equivalentes. Consideramos atentamente el caso de los granos de arena que caen uno por uno ; este goteo deja aparecer unos motivos delimitados por signos. Estudiamos la dinámica del systema y elaboramos unas aproximaciones asinptóticas. Aplicamos nuestros métododos y resultados a otros tipos de configuraciones iniciales. En cada caso estudiado, el tiempo paralelo es inferior al tiempo secuencial en una proporción del orden del número de pilas utilizadas.

Palabras Claves

Autómatas Celulares, Autómatas con Particiones, Reversibilidad, Simulación, Modelo de Pilas de Arena, Tiro de Fichas y Modelo de la Bola de Billar.