Monday, January 30, 2012

1201.5529 (Pablo Arrighi et al.)

A simple block representation of reversible cellular automata with
time-symmetry
   [PDF]

Pablo Arrighi, Vincent Nesme
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.
View original: http://arxiv.org/abs/1201.5529

No comments:

Post a Comment