Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines

Paul MB Vitanyi

The logical depth of a {\em reversible} Turing machine equals the shortest running time of a shortest program for it. This is applied to show that the result in L.F. Antunes, A. So…