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].

, ,
doi.org/10.1016/j.tcs.2019.01.031
Theoretical Computer Science
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Vitányi, P.M.B. (2019). Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines. Theoretical Computer Science. doi:10.1016/j.tcs.2019.01.031