Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata

DOI10.1016/j.tcs.2011.02.022zbMath1216.68176OpenAlexW2067549872MaRDI QIDQ549699

Kenichi Morita

Publication date: 18 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.02.022

zbMATH Keywords

reversible computingcyclic tag systemreversible cellular automatonreversible Turing machineuniversal cellular automaton

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

Clean Reversible Simulations of Ranking Binary Trees ⋮ Invertible behavior in elementary cellular automata with memory ⋮ Language Recognition by Reversible Partitioned Cellular Automata ⋮ Computation in reversible cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Four states are enough!
• Reversible computing and cellular automata -- a survey
• Computation-universality of one-dimensional one-way reversible cellular automata
• Computation and construction universality of reversible cellular automata
• Reversibility and surjectivity problems of cellular automata
• A computation-universal two-dimensional 8-state triangular reversible cellular automaton
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• A Universal Reversible Turing Machine
• HOW TO SIMULATE TURING MACHINES BY INVERTIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA
• Endomorphisms and automorphisms of the shift dynamical system
• Logical Reversibility of Computation