On aperiodic reversible Turing machines (invited talk)

DOI10.1007/978-3-319-99498-7_4OpenAlexW2888248087MaRDI QIDQ1796366FDOQ1796366

Authors: Nicolas Ollinger 

Publication date: 17 October 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-99498-7_4

Recommendations

• A small minimal aperiodic reversible Turing machine
• Some undecidable problems about the trace-subshift associated to a Turing machine
• Periodicity and Immortality in Reversible Computing
• 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

zbMATH Keywords

dynamical systemscellular automataaperiodicityundecidabilityreversible Turing machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Cited In (11)

• Title not available (Why is that?)
• Some undecidable problems about the trace-subshift associated to a Turing machine
• On reversible Turing machines and their function universality
• On immortal configurations in Turing machines
• Undecidability of the speed positiveness problem in reversible and complete Turing machines
• A small minimal aperiodic reversible Turing machine
• Topological mixing notions on Turing machine dynamical systems
• The group of reversible Turing machines
• 2-state 2-symbol Turing machines with periodic support produce regular sets
• Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
• On the presence of periodic configurations in Turing machines and in counter machines.

This page was built for publication: On aperiodic reversible Turing machines (invited talk)

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