2017-11-30

# On the rate of decrease in logical depth

## Publication

### Publication

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

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 |