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 条

[31] COMPUTABILITY OF TOPOLOGICAL ENTROPY: FROM GENERAL SYSTEMS TO TRANSFORMATIONS ON CANTOR SETS AND THE INTERVAL
Gangloff, Silvere
Herrera, Alonso
Rojas, Cristobal
Sablik, Mathieu
DISCRETE AND CONTINUOUS DYNAMICAL SYSTEMS, 2020, 40 (07) : 4259 - 4286
[32] How to Run Turing Machines on Encrypted Data
Goldwasser, Shafi
Kalai, Yael Tauman
Popa, Raluca Ada
Vaikuntanathan, Vinod
Zeldovich, Nickolai
ADVANCES IN CRYPTOLOGY - CRYPTO 2013, PT II, 2013, 8043 : 536 - 553
[33] On relations between properties in transitive Turing machines
Torres-Aviles, Rodrigo
Gajardo, Anahi
Ollinger, Nicolas
NONLINEARITY, 2023, 36 (12) : 6297 - 6323
[34] Asymptotic behavior and halting probability of Turing Machines
D'Abramo, Germano
CHAOS SOLITONS & FRACTALS, 2008, 37 (01) : 210 - 214
[35] On Aperiodic Reversible Turing Machines (Invited Talk)
Ollinger, Nicolas
REVERSIBLE COMPUTATION, RC 2018, 2018, 11106 : 61 - 64
[36] Making Turing Machines Accessible to Blind Students
Crescenzi, Pilu
Rossi, Leonardo
Apollaro, Gianluca
SIGCSE 12: PROCEEDINGS OF THE 43RD ACM TECHNICAL SYMPOSIUM ON COMPUTER SCIENCE EDUCATION, 2011, : 167 - 172
[37] Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Koppula, Venkata
Lewko, Allison Bishop
Waters, Brent
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2015, : 419 - 428
[38] Identification Capacity of Channels With Feedback: Discontinuity Behavior, Super-Activation, and Turing Computability
Boche, Holger
Schaefer, Rafael F.
Poor, H. Vincent
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (10) : 6184 - 6199
[39] Computing the Solution of the Nonlinear Heat Equation on Turing Machines
Lu, Dianchen
Xu, Yuanyuan
2011 INTERNATIONAL CONFERENCE ON COMPUTERS, COMMUNICATIONS, CONTROL AND AUTOMATION (CCCA 2011), VOL III, 2010, : 270 - 273
[40] Simulating Turing machines by P systems with external output
Romero-Jiménez, K
Pérez-Jiménez, MJ
FUNDAMENTA INFORMATICAE, 2002, 49 (1-3) : 273 - 287

← 1 2 3 4 5 →