Periodicity and Immortality in Reversible Computing

DOI10.1007/978-3-540-85238-4_34zbMath1173.68521DBLPconf/mfcs/KariO08OpenAlexW1856886728WikidataQ62045952 ScholiaQ62045952MaRDI QIDQ3599146

Jarkko Kari, Nicolas Ollinger

Publication date: 3 February 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_34

Mathematics Subject Classification ID

Related Items (33)

Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine ⋮ The Group of Reversible Turing Machines ⋮ A small minimal aperiodic reversible Turing machine ⋮ Universal groups of cellular automata ⋮ The Transitivity Problem of Turing Machines ⋮ Topological mixing notions on Turing machine dynamical systems ⋮ On relations between properties in transitive Turing machines ⋮ A physically universal Turing machine ⋮ The periodic domino problem revisited ⋮ An automaton group with undecidable order and Engel problems ⋮ Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version) ⋮ Undecidability of the topological entropy of reversible cellular automata and related problems ⋮ Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$ ⋮ Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata ⋮ Homotopy theory of monoid actions via group actions and an Elmendorf style theorem ⋮ On the conjugacy problem of cellular automata ⋮ On time-symmetry in cellular automata ⋮ About the Domino Problem for Subshifts on Groups ⋮ Automaton (Semi)groups: Wang Tilings and Schreier Tries ⋮ Transitive action on finite points of a full shift and a finitary Ryan’s theorem ⋮ The Undecidability of the Domino Problem ⋮ A note on subgroups of automorphism groups of full shifts ⋮ Computational complexity of finite asynchronous cellular automata ⋮ THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ An exploration of reversible septenary number-conserving cellular automata: a survey of known methods ⋮ Undecidability of the speed positiveness problem in reversible and complete Turing machines ⋮ Decidability in Group Shifts and Group Cellular Automata ⋮ Automata on the plane vs particles and collisions ⋮ Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets ⋮ A Universal Cellular Automaton Without Sensitive Subsystems ⋮ Freezing, Bounded-Change and Convergent Cellular Automata ⋮ Decidability and undecidability in cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• On topological dynamics of Turing machines
• Universality of a reversible two-counter machine
• Theory of cellular automata: a survey
• On the presence of periodic configurations in Turing machines and in counter machines.
• Irreversibility and Heat Generation in the Computing Process
• The undecidability of the Turing machine immortality problem
• Logical Reversibility of Computation

This page was built for publication: Periodicity and Immortality in Reversible Computing