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 条

[21] Improved simulation of nondeterministic Turing machines
Kalyanasundaram, Subrahmanyam
Lipton, Richard J.
Regan, Kenneth W.
Shokrieh, Farbod
THEORETICAL COMPUTER SCIENCE, 2012, 417 : 66 - 73
[22] Computability of entropy and information in classical Hamiltonian systems
Kim, Sungyun
PHYSICS LETTERS A, 2009, 373 (16) : 1409 - 1414
[23] Verified Programming of Turing Machines in Coq
Forster, Yannick
Kunze, Fabian
Wuttke, Maximilian
CPP '20: PROCEEDINGS OF THE 9TH ACM SIGPLAN INTERNATIONAL CONFERENCE ON CERTIFIED PROGRAMS AND PROOFS, 2020, : 114 - 128
[24] A local model of quantum turing machines
Wang, Dong-Sheng
Quantum Information and Computation, 2020, 20 (3-4): : 213 - 229
[25] On the Computability of Continuous Maximum Entropy Distributions with Applications
Leake, Jonathan
Vishnoi, Nisheeth K.
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 930 - 943
[26] An instruction set for reversible Turing machines
Morita, Kenichi
ACTA INFORMATICA, 2021, 58 (04) : 377 - 396
[27] Encodings of Turing machines in linear logic
Clift, James
Murfet, Daniel
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2020, 30 (04) : 379 - 415
[28] Restricted Turing Machines and Language Recognition
Pighizzini, Giovanni
LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, LATA 2016, 2016, 9618 : 42 - 56
[29] Bounded Rationality of Restricted Turing Machines
Chen, Lijie
Tang, Pingzhong
Wang, Ruosong
THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2017, : 444 - 450
[30] Computing power of Turing machines in the framework of unsharp quantum logic
Shang, Yun
Lu, Xian
Lu, Raqian
THEORETICAL COMPUTER SCIENCE, 2015, 598 : 2 - 14

← 1 2 3 4 5 →