Computability of the entropy of one-tape Turing machines

Jeandel, Emmanuel

doi:10.4230/LIPIcs.STACS.2014.421

Document

Computability of the entropy of one-tape Turing machines

Author Emmanuel Jeandel

Part of: Volume: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-03-05

PDF

File

PDF

LIPIcs.STACS.2014.421.pdf

Filesize: 0.52 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2014.421
URN: urn:nbn:de:0030-drops-44767

Subject Classification

Keywords

Turing Machines
Dynamical Systems
Entropy
Crossing Sequences
Automata

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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

Cite As Get BibTex

Emmanuel Jeandel. Computability of the entropy of one-tape Turing machines. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.STACS.2014.421

Author Details

Emmanuel Jeandel

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail