Computability of the entropy of one-tape Turing machines

Author Emmanuel Jeandel



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.421.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Emmanuel Jeandel

Cite AsGet 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

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.
Keywords
  • Turing Machines
  • Dynamical Systems
  • Entropy
  • Crossing Sequences
  • Automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail