37
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Computability of the entropy of one-tape Turing Machines

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Author and article information

          Journal
          2013-02-05
          Article
          1302.1170
          e02f907a-9191-4cf2-b2e7-9202f3f68a37

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          First version (01/08/2012)
          cs.FL cs.CC cs.IT math.DS math.IT
          ccsd

          Numerical methods,Theoretical computer science,Differential equations & Dynamical systems,Information systems & theory

          Comments

          Comment on this article