Paper Info
Title
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
Abstract
The logical depth of a reversible Turing machine equals the shortest running time of a shortest program for it. This is applied to show that the result in [1] is valid notwithstanding the error noted in Corrigendum [7].
Year
DOI
Venue
2019
10.1016/j.tcs.2019.01.031
Theoretical Computer Science
Keywords
Field
DocType
Logical depth,Kolmogorov complexity,Compression
Discrete mathematics,Kolmogorov complexity,Turing machine,Logical depth,Mathematics
Journal
Volume
ISSN
Citations 
778
0304-3975
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Paul Vitányi12130287.76