English

14 Pages

Downloading requires you to have access to the YouScribe library

__
Learn all about the services we offer
__

Description

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.

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

Subjects

Informations

Published by | profil-nechor-2012 |

Reads | 23 |

Language | English |

Report a problem