Computability of the entropy of one-tape Turing machines

DOI10.4230/LIPICS.STACS.2014.421zbMATH Open1359.68073arXiv1302.1170MaRDI QIDQ2965503FDOQ2965503

Authors: Emmanuel Jeandel 

Publication date: 3 March 2017

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.

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

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

zbMATH Keywords

entropydynamical systemsautomataTuring machinescrossing sequences

Mathematics Subject Classification ID

Cited In (13)

• Effect of quantified irreducibility on the computability of subshift entropy
• Undecidability of the topological entropy of reversible cellular automata and related problems
• The transitivity problem of Turing machines
• On entropy and Turing machine with moving tape dynamical model
• Computational power of one-way Turing machines with sublogarithmic memory restrictions
• 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
• Computability of topological entropy: from general systems to transformations on Cantor sets and the interval
• A physically universal Turing machine
• Title not available (Why is that?)
• On relations between properties in transitive 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)