Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Jérôme Durand-Lose

doi:10.46298/dmtcs.2297

Jérôme Durand-Lose - Representing Reversible Cellular Automata with Reversible Block Cellular Automata

dmtcs:2297 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001) - https://doi.org/10.46298/dmtcs.2297

Representing Reversible Cellular Automata with Reversible Block Cellular AutomataConference paper

Authors: Jérôme Durand-Lose ¹

1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis [I3S]

Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks.We prove that any d-dimensional reversible cellular automaton can be exp ressed as thecomposition of d+1 block permutations.We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved by Kari in 1996 (Mathematical System Theory 29).

https://doi.org/10.46298/dmtcs.2297

Source: HAL:hal-01182977v1

Volume: DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)

Section: Proceedings

Published on: January 1, 2001

Imported on: November 21, 2016

Keywords: [INFO]Computer Science [cs], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] Cellular automata, reversibility, block cellular automata, partitioning cellular automata

Bibliographic References

16 Documents citing this article

Hayashi Ani;Josh Brunner;Erik D. Demaine;Jenny Diomidova;Timothy Gomez;et al., 2024, Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More, Lecture notes in computer science, pp. 219-236, 10.1007/978-3-031-63742-1_16.

Eric Goles;Michail-Antisthenis Tsompanas;Andrew Adamatzky;Martin Tegelaar;Han A.B. Wosten;et al., 2020, Computational universality of fungal sandpile automata, arXiv (Cornell University), 384, 22, pp. 126541, 10.1016/j.physleta.2020.126541, http://arxiv.org/abs/2003.08681.

Jérôme Durand-Lose, 2018, Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage, Emergence, complexity and computation, pp. 61-93, 10.1007/978-3-319-73216-9_4.

Norman Margolus, 2018, Finite-State Classical Mechanics, Lecture notes in computer science, pp. 47-60, 10.1007/978-3-319-99498-7_3.

Pablo Arrighi;Simon Martiel, 2017, Quantum causal graph dynamics, arXiv (Cornell University), 96, 2, 10.1103/physrevd.96.024026, http://arxiv.org/abs/1607.06700.

Norman Margolus, 2016, The Ideal Energy of Classical Lattice Dynamics, Emergence, complexity and computation, pp. 59-71, 10.1007/978-3-319-33924-5_3.

Ronaldo de Castro Corrêa;Pedro P. B. de Oliveira, 2016, Partial Reversibility of One-Dimensional Cellular Automata, pp. 120-134, 10.1007/978-3-319-39300-1_10, https://hal.inria.fr/hal-01435024.

Norman Margolus, 2015, The Ideal Energy of Classical Lattice Dynamics, arXiv (Cornell University), pp. 169-180, 10.1007/978-3-662-47221-7_13, http://arxiv.org/abs/1503.00713.

Pablo Arrighi;Gilles Dowek, 2012, Causal graph dynamics, Information and Computation, 223, pp. 78-93, 10.1016/j.ic.2012.10.019.

Klaus Sutner, 2009, Classification of Cellular Automata, Cellular Automata, pp. 185-200, 10.1007/978-1-4939-8700-9_50.

Maurice Margenstern, 2009, Surprising Areas in the Quest for Small Universal Devices, Electronic Notes in Theoretical Computer Science, 225, pp. 201-220, 10.1016/j.entcs.2008.12.075, https://doi.org/10.1016/j.entcs.2008.12.075.

Anas N. Al-Rabadi, 2008, Modeling and Processing Using Reversible Conservative Noisy Elementary Cellular Automata Circuits and their M-Ary Quantum Computing, Intelligent Automation & Soft Computing, 14, 2, pp. 177-206, 10.1080/10798587.2008.10642990.

Bastien Chopard;Jean-Luc Falcone;Ranaivo Razakanirina;Alfons Hoekstra;Alfonso Caiazzo, 2008, On the Collision-Propagation and Gather-Update Formulations of a Cellular Automata Rule, Lecture notes in computer science, pp. 144-151, 10.1007/978-3-540-79992-4_19.

Stephane Marconi;Bastien Chopard, 2006, Discrete Physics, Cellular Automata and Cryptography, Lecture notes in computer science, pp. 617-626, 10.1007/11861201_72.

Jarkko Kari, 2005, Theory of cellular automata: A survey, Theoretical Computer Science, 334, 1-3, pp. 3-33, 10.1016/j.tcs.2004.11.021.

Jérôme Durand-Lose, 2002, Computing Inside the Billiard Ball Model, pp. 135-160, 10.1007/978-1-4471-0129-1_6.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 629 times.

This article's PDF has been downloaded 485 times.