Computability of the entropy of one-tape Turing machines

被引:9
|
作者
Jeandel, Emmanuel [1 ]
机构
[1] LORIA, UMR 7503, Campus Sci, Vandoeuvre Les Nancy, France
来源
31ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2014) | 2014年 / 25卷
关键词
Turing Machines; Dynamical Systems; Entropy; Crossing Sequences; Automata; DYNAMICS; SHIFTS;
D O I
10.4230/LIPIcs.STACS.2014.421
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 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.
引用
收藏
页码:421 / 432
页数:12
相关论文
共 50 条
  • [1] The element distinctness problem on one-tape Turing machines
    Szepietowski, A
    INFORMATION PROCESSING LETTERS, 1996, 59 (04) : 203 - 206
  • [2] Bounds for the Element Distinctness Problem on one-tape Turing machines
    Petersen, H
    INFORMATION PROCESSING LETTERS, 2002, 81 (02) : 75 - 79
  • [3] Feedback Turing Computability, and Turing Computability as Feedback
    Ackerman, Nathanael L.
    Freer, Cameron E.
    Lubarsky, Robert S.
    2015 30TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2015, : 523 - 534
  • [4] A formalization of multi-tape Turing machines
    Asperti, Andrea
    Ricciotti, Wilmer
    THEORETICAL COMPUTER SCIENCE, 2015, 603 : 23 - 42
  • [5] An introduction to feedback Turing computability
    Ackerman, Nathanael L.
    Freer, Cameron E.
    Lubarsky, Robert S.
    JOURNAL OF LOGIC AND COMPUTATION, 2020, 30 (01) : 27 - 60
  • [6] EFFECT OF QUANTIFIED IRREDUCIBILITY ON THE COMPUTABILITY OF SUBSHIFT ENTROPY
    Gangloff, Silvere
    de Menibus, Benjamin Hellouin
    DISCRETE AND CONTINUOUS DYNAMICAL SYSTEMS, 2019, 39 (04) : 1975 - 2000
  • [7] Minds, Machines and Turing
    S. Harnad
    Journal of Logic, Language and Information, 2000, 9 (4) : 425 - 445
  • [8] Turing Machines with Atoms
    Bojanczyk, Mikolaj
    Klin, Bartek
    Lasota, Slawomir
    Torunczyk, Szymon
    2013 28TH ANNUAL IEEE/ACM SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2013, : 183 - 192
  • [9] Zigzags in Turing Machines
    Gajardo, Anahi
    Guillon, Pierre
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2010, 6072 : 109 - +
  • [10] Symmetric Instruction Machines and Symmetric Turing Machines
    Burgin, Mark
    Schroeder, Marcin J.
    PHILOSOPHIES, 2025, 10 (01)