On the rate of decrease in logical depth
Theoretical Computer Science , Volume 702 p. 60- 64
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.
|Theoretical Computer Science|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam, The Netherlands|
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