A small minimal aperiodic reversible Turing machine

DOI10.1016/J.JCSS.2016.10.004MaRDI QIDQ340590zbMATH OpenOpenAlexFDO

Authors Julien Cassaigne, Nicolas Ollinger, Rodrigo Torres-Avilés

Publication date 14 November 2016

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.2016.10.004

zbMATH Keywords

discrete dynamical systemssymbolic dynamicsTuring machines

Mathematics Subject Classification ID

Symbolic dynamics (37B10)

Recommendations

• Small deterministic Turing machines
• Universal reversible Turing machines with a small number of tape symbols
• Minimal reversible deterministic finite automata
• Minimal reversible deterministic finite automata
• Minimal and reduced reversible automata
• Minimal and Reduced Reversible Automata
• A simple and efficient universal reversible Turing machine
• Small universal Turing machines
• A Universal Reversible Turing Machine
• On aperiodic reversible Turing machines (invited talk)

Cites work

• Computability of the entropy of one-tape Turing machines
• On entropy and Turing machine with moving tape dynamical model
• On the presence of periodic configurations in Turing machines and in counter machines.
• On time-symmetry in cellular automata
• On topological dynamics of Turing machines
• One head machines from a symbolic approach
• Periodicity and Immortality in Reversible Computing
• The undecidability of the Turing machine immortality problem
• Zigzags in Turing Machines

Cited in

(14)

• On aperiodic reversible Turing machines (invited talk)
• On the presence of periodic configurations in Turing machines and in counter machines.
• Undecidability of the speed positiveness problem in reversible and complete Turing machines
• Distortion in automorphisms of expansive systems
• 2-state 2-symbol Turing machines with periodic support produce regular sets
• Topological mixing notions on Turing machine dynamical systems
• On immortal configurations in Turing machines
• The transitivity problem of Turing machines
• The group of reversible Turing machines
• Some undecidable problems about the trace-subshift associated to a Turing machine
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• On relations between properties in transitive Turing machines
• Distortion element in the automorphism group of a full shift
• A categorical approach to reversible Turing machines and Brin-Thompson groups

This page was built for publication: A small minimal aperiodic reversible Turing machine

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