Periodicity and Immortality in Reversible Computing
From MaRDI portal
Publication:3599146
DOI10.1007/978-3-540-85238-4_34zbMath1173.68521WikidataQ62045952 ScholiaQ62045952MaRDI QIDQ3599146
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
Related Items
About the Domino Problem for Subshifts on Groups, Automaton (Semi)groups: Wang Tilings and Schreier Tries, A note on subgroups of automorphism groups of full shifts, Universal groups of cellular automata, The Undecidability of the Domino Problem, Decidability in Group Shifts and Group Cellular Automata, Transitive action on finite points of a full shift and a finitary Ryan’s theorem, THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE, A Universal Cellular Automaton Without Sensitive Subsystems, Freezing, Bounded-Change and Convergent Cellular Automata, On relations between properties in transitive Turing machines, 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, 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, A small minimal aperiodic reversible Turing machine, The periodic domino problem revisited, On time-symmetry in cellular automata, Computational complexity of finite asynchronous cellular automata, Automata on the plane vs particles and collisions, An automaton group with undecidable order and Engel problems, Permutive one-way cellular automata and the finiteness problem for automaton groups, Undecidability of the speed positiveness problem in reversible and complete Turing machines, Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets, On the conjugacy problem of cellular automata, Topological mixing notions on Turing machine dynamical systems, A physically universal Turing machine, Decidability and undecidability in cellular automata, The Transitivity Problem of Turing Machines, Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$, The Group of Reversible Turing Machines, Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
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