Computability of the entropy of one-tape Turing machines

DOI10.4230/LIPICS.STACS.2014.421MaRDI QIDQ2965503zbMATH OpenFDO

Authors Emmanuel Jeandel

Publication date 3 March 2017

Full work available at URL https://arxiv.org/abs/1302.1170

zbMATH Keywords

entropydynamical systemsautomataTuring machinescrossing sequences

Mathematics Subject Classification ID

Abstract: We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision $epsilon$. This is contrary to popular belief, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.

Recommendations

• On entropy and Turing machine with moving tape dynamical model
• Undecidability of the speed positiveness problem in reversible and complete Turing machines
• On computing the topological entropy of one-sided cellular automata
• On the computability of the topological entropy of subshifts
• Some undecidable problems about the trace-subshift associated to a Turing machine

Cited in

(13)

• Undecidability of the topological entropy of reversible cellular automata and related problems
• Computational power of one-way Turing machines with sublogarithmic memory restrictions
• Undecidability of the speed positiveness problem in reversible and complete Turing machines
• scientific article; zbMATH DE number 3968573 (Why is no real title available?)
• Computability of topological entropy: from general systems to transformations on Cantor sets and the interval
• On entropy and Turing machine with moving tape dynamical model
• On relations between properties in transitive Turing machines
• A physically universal Turing machine
• Effect of quantified irreducibility on the computability of subshift entropy
• Topological mixing notions on Turing machine dynamical systems
• A small minimal aperiodic reversible Turing machine
• The transitivity problem of Turing machines
• The group of reversible Turing machines

This page was built for publication: Computability of the entropy of one-tape Turing machines

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