Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2017.08.012 | Theoretical Computer Science |
Keywords | Field | DocType |
Logical depth,Kolmogorov complexity,Compression | Algorithmic probability,Discrete mathematics,Combinatorics,Busy beaver,Existential quantification,Kolmogorov complexity,Logical depth,Mathematics,Computable function,Computation | Journal |
Volume | ISSN | Citations |
702 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luis Filipe Coelho Antunes | 1 | 26 | 8.42 |
| Andre Souto | 2 | 29 | 9.29 |
| Paul Vitányi | 3 | 2130 | 287.76 |