Affordable Access

Intrinsic Universality of a 1-Dimensional Reversible Cellular Automaton

Authors
  • Durand-Lose, Jérôme
Publication Date
Jan 01, 1997
Source
HAL-UPMC
Keywords
Language
English
License
Unknown
External links

Abstract

This paper deals with simulation and reversibility in the context of Cellular Automata (CA). We recall the definitions of {CA} and of the Block (BCA) and Partitioned (PCA) subclasses. We note that {PCA} simulate {CA}. A simulation of reversible {CA} (RCA) with reversible {PCA} is built contradicting the intuition of known undecidability results. We build a {1d-RCA} which is intrinsically universal, i.e., able to simulate any 1d-R-CA.

Report this publication

Statistics

Seen <100 times