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

, ,
Theoretical Computer Science
Centrum Wiskunde & Informatica, Amsterdam, 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