Computer Science – Discrete Mathematics
Scientific paper
2012-01-26
Computer Science
Discrete Mathematics
6 pages, 3 figures, Automata 2011
Scientific paper
Reversible Cellular Automata (RCA) are a physics-like model of computation consisting of an array of identical cells, evolving in discrete time steps by iterating a global evolution G. Further, G is required to be shift-invariant (it acts the same everywhere), causal (information cannot be transmitted faster than some fixed number of cells per time step), and reversible (it has an inverse which verifies the same requirements). An important, though only recently studied special case is that of Time-symmetric Cellular Automata (TSCA), for which G and its inverse are related via a local operation. In this note we revisit the question of the Block representation of RCA, i.e. we provide a very simple proof of the existence of a reversible circuit description implementing G. This operational, bottom-up description of G turns out to be time-symmetric, suggesting interesting connections with TSCA. Indeed we prove, using a similar technique, that a wide class of them admit an Exact block representation (EBR), i.e. one which does not increase the state space.
Arrighi Pablo
Nesme Vincent
No associations
LandOfFree
A simple block representation of reversible cellular automata with time-symmetry does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A simple block representation of reversible cellular automata with time-symmetry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A simple block representation of reversible cellular automata with time-symmetry will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-445720