On time-symmetry in cellular automata

DOI10.1016/J.JCSS.2012.01.006zbMATHOpenAlexWikidataMaRDI QIDQ439976FDO

Authors 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

reversibilitycellular automatadecidabilityuniversalitytime-symmetry

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• Universal time-symmetric number-conserving cellular automaton
• Selfsimilarity, simulation and spacetime symmetries
• Reversibility of 2D cellular automata is undecidable
• Reversibility and surjectivity problems of cellular automata
• Cellular automata reversible over limit set

Cites work

• scientific article; zbMATH DE number 3898247 (Why is no real title available?)
• Bulking II: Classifications of cellular automata
• Complexity of Langton's ant
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Developments in Language Theory
• Endomorphisms and automorphisms of the shift dynamical system
• Invertible cellular automata: A review
• Periodicity and Immortality in Reversible Computing
• Representation of reversible cellular automata with block permutations
• Reversibility and surjectivity problems of cellular automata
• Reversibility of 2D cellular automata is undecidable
• The undecidability of the domino problem
• Time-reversal symmetry in dynamical systems: a survey

Cited in

(17)

• Decidability and undecidability in cellular automata
• Gliders in the game of life and in a reversible cellular automaton
• Finite automata with undirected state graphs
• Freezing, bounded-change and convergent cellular automata
• Constructive chaos by cellular automata and possible sources of an arrow of time
• scientific article; zbMATH DE number 5994090 (Why is no real title available?)
• Characterizing asymptotic randomization in abelian cellular automata
• Fractional-time states of cellular automata
• Universal time-symmetric number-conserving cellular automaton
• A toy model provably featuring an arrow of time without past hypothesis
• On relations between properties in transitive Turing machines
• Cold dynamics in cellular automata: a tutorial
• Aspects of reversibility for classical automata
• Statistical equilibrium in deterministic cellular automata
• Selfsimilarity, simulation and spacetime symmetries
• A small minimal aperiodic reversible Turing machine
• A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule

This page was built for publication: On time-symmetry in cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439976)