The transitivity problem of Turing machines

DOI10.1007/978-3-662-48057-1_18MaRDI QIDQ2946339zbMATH OpenOpenAlexFDO

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

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

computabilitydiscrete dynamical systemsreversible computingsymbolic dynamicstopological dynamics

Mathematics Subject Classification ID

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

Recommendations

• Topological mixing notions on Turing machine dynamical systems
• On topological dynamics of Turing machines
• A small minimal aperiodic reversible Turing machine
• Some undecidable problems about the trace-subshift associated to a Turing machine
• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine

Cites work

• A small minimal aperiodic reversible Turing machine
• Computability of the entropy of one-tape Turing machines
• Generalized shifts: unpredictability and undecidability in dynamical systems
• scientific article; zbMATH DE number 3898247 (Why is no real title available?)
• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On entropy and Turing machine with moving tape dynamical model
• On the presence of periodic configurations in Turing machines and in counter machines.
• On topological dynamics of Turing machines
• One head machines from a symbolic approach
• Periodicity and Immortality in Reversible Computing
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata
• Some results on the generalized star-height problem
• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
• Zigzags in Turing Machines

Cited in

(14)

• On topological dynamics of Turing machines
• On the transition graphs of Turing machines.
• Undecidability of the speed positiveness problem in reversible and complete Turing machines
• Topological mixing notions on Turing machine dynamical systems
• On Turing machines, groupoids, and Atiyah problem
• On entropy and Turing machine with moving tape dynamical model
• Some undecidable problems about the trace-subshift associated to a Turing machine
• scientific article; zbMATH DE number 1738661 (Why is no real title available?)
• A driven ifs representation of Turing machines
• On relations between properties in transitive Turing machines
• Undecidability of the topological entropy of reversible cellular automata and related problems
• The group of reversible Turing machines: subgroups, generators, and computability
• A categorical approach to reversible Turing machines and Brin-Thompson groups
• One head machines from a symbolic approach

This page was built for publication: The transitivity problem of Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946339)