On the Logical Depth Function and the Running Time of Shortest Programs
Luís Filipe Antunes, André Souto · 2013
For a nite binary string x its logical depth d for signicance b is the shortest running time of a program for x of length K(x) +b. There is another denition of logical depth. We give a new proof that the two versions are close. There is an innite 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 signicance