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 AutomataArticle

Authors: Jérôme Durand-Lose ¹

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

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 <i>(Physica D 45)</i> improved by Kari in 1996 <i>(Mathematical System Theory 29)</i>.

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: Cellular automata,reversibility,block cellular automata,partitioning cellular automata,[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]

Bibliographic References

15 Documents citing this article

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, Emergence, complexity and computation, Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage, pp. 61-93, 2018, 10.1007/978-3-319-73216-9_4.

Norman Margolus, arXiv (Cornell University), Finite-State Classical Mechanics, pp. 47-60, 2018, 10.1007/978-3-319-99498-7_3, http://arxiv.org/abs/1807.04437.

Pablo Arrighi;Simon Martiel, 2017, Quantum causal graph dynamics, 96, 2, 10.1103/physrevd.96.024026, https://hal.science/hal-01785461.

Norman Margolus, arXiv (Cornell University), The Ideal Energy of Classical Lattice Dynamics, pp. 59-71, 2016, 10.1007/978-3-319-33924-5_3, https://arxiv.org/abs/1503.00713.

Ronaldo de Castro Corrêa;Pedro P. B. de Oliveira, Lecture notes in computer science, Partial Reversibility of One-Dimensional Cellular Automata, pp. 120-134, 2016, 10.1007/978-3-319-39300-1_10, https://doi.org/10.1007/978-3-319-39300-1_10.

Norman Margolus, Lecture notes in computer science, The Ideal Energy of Classical Lattice Dynamics, pp. 169-180, 2015, 10.1007/978-3-662-47221-7_13, https://doi.org/10.1007/978-3-662-47221-7_13.

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

Klaus Sutner, Springer eBooks, Classification of Cellular Automata, pp. 185-200, 2009, 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, Lecture notes in computer science, On the Collision-Propagation and Gather-Update Formulations of a Cellular Automata Rule, pp. 144-151, 2008, 10.1007/978-3-540-79992-4_19.

Stephane Marconi;Bastien Chopard, Lecture notes in computer science, Discrete Physics, Cellular Automata and Cryptography, pp. 617-626, 2006, 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, Springer eBooks, Computing Inside the Billiard Ball Model, pp. 135-160, 2002, 10.1007/978-1-4471-0129-1_6.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 455 times.

This article's PDF has been downloaded 301 times.