Title: Reversibility in Turing machine topological models
Abstract: Reversibility is equivalent to surjectivity within Turing machine topological systems. Although reversibility is a decidable property in Turing machines, a proper reverse Turing machine does not exist in the standard Turing model. Traditional solutions to this problem imply reducing the speed of the reversible Turing machine, therefore affecting its dynamics. Also, traces of topological dynamical systems of Turing machines can be surjective when the original Turing machine is not. A solution is a reversible Turing machine, considering a shift in the tape depending on the actual state, and also it is proven that surjectivity is undecidable for Turing machine subshifts only when the radius is 0.
Publication Year: 2022
Publication Date: 2022-11-21
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot