Intrinsic universality of a 1-dimensional reversible Cellular Automaton

DOI10.1007/BFB0023479zbMath1498.68179MaRDI QIDQ5048944

Jérôme O. Durand-Lose

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items (7)

Cellular automata universality revisited ⋮ An Intrinsically Universal Family of Causal Graph Dynamics ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ Intrinsically universal \(n\)-dimensional quantum cellular automata ⋮ Simulation limitations of affine cellular automata ⋮ The complexity of iterated reversible computation ⋮ Reversible space-time simulation of cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Reversible simulation of one-dimensional irreversible cellular automata
• Reversibility of 2D cellular automata is undecidable
• Invertible cellular automata: A review
• Computation-universality of one-dimensional one-way reversible cellular automata
• Computation and construction universality of reversible cellular automata
• A universal cellular automaton in quasi-linear time and its S-m-n form
• Reversibility and surjectivity problems of cellular automata
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Representation of reversible cellular automata with block permutations
• Reversible cellular automaton able to simulate any other reversible one using partitioning automata
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Endomorphisms and automorphisms of the shift dynamical system
• Logical Reversibility of Computation

This page was built for publication: Intrinsic universality of a 1-dimensional reversible Cellular Automaton