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 . This is counterintuitive, 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.
@InProceedings{jeandel:LIPIcs.STACS.2014.421, author = {Jeandel, Emmanuel}, title = {{Computability of the entropy of one-tape Turing machines}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {421--432}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.421}, URN = {urn:nbn:de:0030-drops-44767}, doi = {10.4230/LIPIcs.STACS.2014.421}, annote = {Keywords: Turing Machines, Dynamical Systems, Entropy, Crossing Sequences, Automata} }
Feedback for Dagstuhl Publishing