The Transitivity Problem of Turing Machines

DOI10.1007/978-3-662-48057-1_18zbMath1465.68072OpenAlexW2285345516MaRDI QIDQ2946339

Rodrigo Torres-Avilés, Anahí Gajardo, Nicolas Ollinger

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48057-1_18

zbMATH Keywords

topological dynamicssymbolic dynamicsdiscrete dynamical systemscomputabilityreversible computing

Mathematics Subject Classification ID

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

Related Items (4)

Topological mixing notions on Turing machine dynamical systems ⋮ On relations between properties in transitive Turing machines ⋮ Undecidability of the topological entropy of reversible cellular automata and related problems ⋮ Undecidability of the speed positiveness problem in reversible and complete Turing machines

Cites Work

• A small minimal aperiodic reversible Turing machine
• One head machines from a symbolic approach
• Some results on the generalized star-height problem
• On topological dynamics of Turing machines
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• On the presence of periodic configurations in Turing machines and in counter machines.
• Computability of the entropy of one-tape Turing Machines
• On entropy and Turing machine with moving tape dynamical model
• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
• Zigzags in Turing Machines
• Periodicity and Immortality in Reversible Computing
• Generalized shifts: unpredictability and undecidability in dynamical systems
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Transitivity Problem of Turing Machines