On time-symmetry in cellular automata

DOI10.1016/j.jcss.2012.01.006zbMath1244.68055OpenAlexW1975307939WikidataQ62045918 ScholiaQ62045918MaRDI QIDQ439976

Anahí Gajardo, Jarkko Kari, Andrés Moreira

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2012.01.006

zbMATH Keywords

cellular automatauniversalitydecidabilityreversibilitytime-symmetry

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

A small minimal aperiodic reversible Turing machine ⋮ Statistical Equilibrium in Deterministic Cellular Automata ⋮ Aspects of Reversibility for Classical Automata ⋮ On relations between properties in transitive Turing machines ⋮ Cold dynamics in cellular automata: a tutorial ⋮ Finite automata with undirected state graphs ⋮ A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule ⋮ Characterizing asymptotic randomization in abelian cellular automata ⋮ Gliders in the game of life and in a reversible cellular automaton ⋮ Freezing, Bounded-Change and Convergent Cellular Automata ⋮ Decidability and undecidability in cellular automata

Cites Work

• Unnamed Item
• Bulking II: Classifications of cellular automata
• Reversibility of 2D cellular automata is undecidable
• Invertible cellular automata: A review
• Time-reversal symmetry in dynamical systems: a survey
• Reversibility and surjectivity problems of cellular automata
• Complexity of Langton's ant
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Periodicity and Immortality in Reversible Computing
• Representation of reversible cellular automata with block permutations
• Developments in Language Theory
• Endomorphisms and automorphisms of the shift dynamical system
• The undecidability of the domino problem