Laboratoire Bordelais de Recherche en Informatique

Niveau: Supérieur
Laboratoire Bordelais de Recherche en Informatique, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, 33 405 Talence Cedex, France. Rapport de Recherche Numéro 1177-97 Reversible space-time simulation of cellular automata Jérôme O. Durand-Lose 1 LaBRI, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, F-33 405 Talence Cedex, France. We briey recall the denitions of Cellular automata (ca), simulation, re- versibility and Partitioned cellular automata (pca) as dened by Morita. We call the sequence of the iterated congurations of a conguration a space-time diagram. We dene an embedding relation between space-time diagrams and a space-time simulation relation between ca. We built a space-time simulation of any ca by a reversible pca (r-pca). Finally, we state our main result: there are reversible ca able to space-time simulate any ca of the same dimension. Key words: Cellular automata, space-time simulation, intrinsic universality and reversibility. 1 Introduction Reversibility corresponds to the conservation of information and energy. It allows unambigu- ous backtracking. In computer science, reversible is studied in order to design computers which would waste less energy.

• diagram gener


• over


• cellular automata


• any space-time


• time simulation


• local function


• generates any diagram


• various ways


• simulate any