Depth as Randomness Deficiency

Depth of an object concerns a tradeoff between computation time and excess of pro-gram length over the shortest program length required to obtain the object. It gives an unconditional lower bound on the computation time from a given program in absence of auxiliary information. Variants known as “logical depth ” and “computational depth”, are expressed in Kolmogorov complexity theory. In this article we derive quantitative relation between logical depth and computational depth and unify the different “depth ” notions by relating them to A. Kolmogorov and L. Levin’s fruitful notion of “randomness deficiency”. Subsequently, we revisit the computa-tional depth of infinite strings, introducing the notion of super deep sequences and relate it with other approaches.