Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata
From MaRDI portal
Publication:549699
DOI10.1016/J.TCS.2011.02.022zbMATH Open1216.68176OpenAlexW2067549872MaRDI QIDQ549699FDOQ549699
Authors: 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
Recommendations
- Simple universal one-dimensional reversible cellular automata
- Reversible simulation of one-dimensional irreversible cellular automata
- A Universal Reversible Turing Machine
- Computation-universality of one-dimensional one-way reversible cellular automata
- Constructing reversible Turing machines in a reversible and conservative elementary triangular cellular automaton
reversible computingcyclic tag systemreversible cellular automatonreversible Turing machineuniversal cellular automaton
Cites Work
- Universality in elementary cellular automata
- Endomorphisms and automorphisms of the shift dynamical system
- Logical Reversibility of Computation
- Four states are enough!
- Reversible computing and cellular automata -- a survey
- Reversibility and surjectivity problems of cellular automata
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tesselations with local transformations
- A Universal Reversible Turing Machine
- Title not available (Why is that?)
- Computation and construction universality of reversible cellular automata
- A computation-universal two-dimensional 8-state triangular reversible cellular automaton
- Computation-universality of one-dimensional one-way reversible cellular automata
- HOW TO SIMULATE TURING MACHINES BY INVERTIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA
- Simple universal one-dimensional reversible cellular automata
Cited In (7)
- Language recognition by reversible partitioned cellular automata
- Computation in reversible cellular automata
- Simple universal one-dimensional reversible cellular automata
- Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases \(f_{i_-}1\)
- Clean reversible simulations of ranking binary trees
- Constructing reversible Turing machines in a reversible and conservative elementary triangular cellular automaton
- Invertible behavior in elementary cellular automata with memory
This page was built for publication: Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549699)
