Undecidability of the speed positiveness problem in reversible and complete Turing machines

DOI10.1016/j.jcss.2021.04.007OpenAlexW3163342729MaRDI QIDQ2040026

Rodrigo Torres-Avilés

Publication date: 6 July 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2021.04.007

zbMATH Keywords

dynamical systemsTuring machineblank tape halting problemmaximum speed

Mathematics Subject Classification ID

Topological entropy (37B40) Symbolic dynamics (37B10) Turing machines and related notions (03D10) Other nonclassical models of computation (68Q09) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• A small minimal aperiodic reversible Turing machine
• Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines
• One head machines from a symbolic approach
• On topological dynamics of Turing machines
• Universality of a reversible two-counter machine
• Distortion in one-head machines and cellular automata
• On the presence of periodic configurations in Turing machines and in counter machines.
• On Immortal Configurations in Turing Machines
• The Transitivity Problem of Turing Machines
• Computability of the entropy of one-tape Turing Machines
• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
• Periodicity and Immortality in Reversible Computing
• The undecidability of the Turing machine immortality problem
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Undecidability of the speed positiveness problem in reversible and complete Turing machines