2012/01/26 by Pablo Arrighi, Vincent Nesme, Arrighi, Pablo +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #37B15 #37N20 #68Q80 #B.6.1 #Cellular Automata and Applications #DNA and Biological Computing #Discrete Mathematics (cs.DM) #F.1.1 #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1201.5529
openalex publication_date 2012/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Reversible Cellular Automata (RCA) are a physics-like model of computation\nconsisting of an array of identical cells, evolving in discrete time steps by\niterating a global evolution G. Further, G is required to be shift-invariant\n(it acts the same everywhere), causal (information cannot be transmitted faster\nthan some fixed number of cells per time step), and reversible (it has an\ninverse which verifies the same requirements). An important, though only\nrecently studied special case is that of Time-symmetric Cellular Automata\n(TSCA), for which G and its inverse are related via a local operation. In this\nnote we revisit the question of the Block representation of RCA, i.e. we\nprovide a very simple proof of the existence of a reversible circuit\ndescription implementing G. This operational, bottom-up description of G turns\nout to be time-symmetric, suggesting interesting connections with TSCA. Indeed\nwe prove, using a similar technique, that a wide class of them admit an Exact\nblock representation (EBR), i.e. one which does not increase the state space.\n