Name
Abstract | ||
|---|---|---|
For a finite binary string $x$ its logical depth $d$ for significance $b$ is the shortest running time of a program for $x$ of length $K(x)+b$. There is another definition of logical depth. We give a new proof that the two versions are close. There is an infinite sequence of strings of consecutive lengths such that for every string there is a $b$ such that incrementing $b$ by 1 makes the associated depths go from incomputable to computable. The maximal gap between depths resulting from incrementing appropriate $b$'s by 1 is incomputable. The size of this gap is upper bounded by the Busy Beaver function. Both the upper and the lower bound hold for the depth with significance 0. As a consequence, the minimal computation time of the associated shortest programs rises faster than any computable function but not so fast as the Busy Beaver function. |
Year | Venue | Field |
|---|---|---|
2013 | arXiv: Computational Complexity | Discrete mathematics,Combinatorics,Busy beaver,Sequence,Upper and lower bounds,Binary strings,Logical depth,Mathematics,Computable function,Bounded function,Computation |
DocType | Volume | Citations |
Journal | abs/1301.4451 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luis Filipe Coelho Antunes | 1 | 26 | 8.42 |
| Andre Souto | 2 | 2 | 2.42 |
| A. Teixeira | 3 | 0 | 0.34 |
| Paul Vitányi | 4 | 2130 | 287.76 |