The logical depth with significance b of a string x is the shortest running time of a program for x that can be compressed by at most b bits. Another definition is based on algorithmic probability. We give a simple new proof for the known relation between the two definitions. We also prove the following: Given a string we can consider the maximal decrease in logical depth when the significance parameter increases by 1. There exists a sequence of strings of lengths n=1,2,..., such that this maximal decrease as a function of n rises faster than any computable function but not as fast as the Busy Beaver function. This holds also for the computation times of the shortest programs of these strings.

Additional Metadata
Keywords Compression, Kolmogorov complexity, Logical depth
Persistent URL dx.doi.org/10.1016/j.tcs.2017.08.012
Journal Theoretical Computer Science
Citation
Antunes, L.F, Souto, A, & Vitányi, P.M.B. (2017). On the rate of decrease in logical depth. Theoretical Computer Science, 702, 60–64. doi:10.1016/j.tcs.2017.08.012