For a finite binary string @math its logical depth @math for significance @math is the shortest running time of a program for @math of length @math . 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 @math such that incrementing @math by 1 makes the associated depths go from incomputable to computable. The maximal gap between depths resulting from incrementing appropriate @math '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.
The minimum time to compute a string by a @math -incompressible program was first considered in @cite_9 . This minimum time is called the logical depth at significance @math of the string concerned. Definitions, variations, discussion and early results can be found in the given reference. A more formal treatment as well as an intuitive approach was given in the textbook @cite_6 , Section 7.7. In @cite_8 the notion of computational depth is defined as @math (see definitions below). This would equal the negative logarithm of the expression @math in Definition if the following were proved. Since @cite_7 proved in the so-called Coding Theorem that @math up to a constant additive term it remains to prove @math up to a small additive term. The last equality is a major open problem in Kolmogorov complexity theory, see @cite_6 Exercises 7.6.3 and 7.6.4.
@cite_9 @cite_7 @cite_6 @cite_8
2281664623 33555989 1638203394 2072053479
Some mathematical and natural objects (a random sequence, a sequence of zeros, a perfect crystal, a gas) are intuitively trivial, while others (e.g. the human body, the digits of π) contain internal evidence of a nontrivial causal history. We formalize this distinction by defining an object’s “logical depth” as the time required by a standard universal Turing machine to generate it from an input that is algorithmically random (i.e. Martin-Lof random). This definition of depth is shown to be reasonably machineindependent, as well as obeying a slow-growth law: deep objects cannot be quickly produced from shallow ones by any deterministic process, nor with much probability by a probabilistic process, but can be produced slowly. Next we apply depth to the physical problem of “self-organization,” inquiring in particular under what conditions (e.g. noise, irreversibility, spatial and other symmetries of the initial conditions and equations of motion) statistical-mechanical model systems can imitate computers well enough to undergo unbounded increase of depth in the limit of infinite space and time. The book is outstanding and admirable in many respects. ... is necessary reading for all kinds of readers from undergraduate students to top authorities in the field. Journal of Symbolic Logic Written by two experts in the field, this is the only comprehensive and unified treatment of the central ideas and their applications of Kolmogorov complexity. The book presents a thorough treatment of the subject with a wide range of illustrative applications. Such applications include the randomness of finite objects or infinite sequences, Martin-Loef tests for randomness, information theory, computational learning theory, the complexity of algorithms, and the thermodynamics of computing. It will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. The book is self-contained in that it contains the basic requirements from mathematics and computer science. Included are also numerous problem sets, comments, source references, and hints to solutions of problems. New topics in this edition include Omega numbers, KolmogorovLoveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, Shannon information and others. We introduce Computational Depth, a measure for the amount of "nonrandom" or "useful" information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth: • Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. We show that a Turing machine M runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, M uses time exponential in the basic computational depth of x. • Sublinear-time Computational Depth and the resulting concept of Shallow Sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences. We show that every computable set that is reducible to a shallow set has polynomial-size circuits. • Distinguishing Computational Depth, measuring when strings are easier to recognize than to produce. We show that if a Boolean formula has a nonnegligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently.