Kolmogorov Complexity

Collection	GlossariumBITri
Author	Mark Burgin
Editor	Mark Burgin
Year	2010
Volume	1
Number	1
ID	13
Object type	Concept
Domain	Ait Coding Theory Complexity Theory Computer Science
es	Complejidad de Kolmogorov
fr	Complexité de Kolmogorov
de	Kolmogorow-Komplexität

Absolute and relative complexity measures

Kolmogorov complexity is an algorithmic measure or measure of algorithmic information. It is defined for constructive objects, such as words in some alphabet. If x is a word, then the original Kolmogorov complexity C(x) of a word x (also denoted by K(x)) is taken to be equal to:

the size of the shortest program (in number of symbols) for a universal Turing machine U that without additional data, computes the string x and terminates.

As Turing machines are recursive algorithms, the original Kolmogorov complexity C(x) is a recursive complexity measure.

This measure is called absolute Kolmogorov complexity because Kolmogorov complexity has also a relative form C(x | y). Namely, the relative Kolmogorov complexity C(x | y) of the word x relative to the word y is taken to be equal to:

the size of the shortest program (in number of symbols) for a universal Turing machine U that with y as its input, computes the string x and terminates.

The relative Kolmogorov complexity C(x | y) allows one to find the algorithmic quantity I(y ; x) of information in a word y about a word x. Namely, we have

I(y ; x) = C(x) - C(x | y)

Complexity with respect to an algorithm

The Kolmogorov complexity C_A(x) of an object (word) x with respect to an algorithm A is defined as

C_A(x) = min {l(p); A(p) = x}

in the case when there is a word p such that A(p) = x;

otherwise C_A(x) is not defined.

If the Church-Turing Thesis (Turing Halting Theorem) is accepted, then any algorithm is modeled by a Turing machine and Kolmogorov complexity is considered only for Turing machines.

Absolute Kolmogorov complexity

Solomonoff (1964), Kolmogorov (1965), and Chaitin (1969) proved that there is an invariant up to some additive constant Kolmogorov complexity C(x). It is called absolute Kolmogorov complexity because there is also relative Kolmogorov complexity C(x|y). Namely, there is a Turing machine U such that for any Turing machine T, there is a constant c_UT such that for all words x, we have

C_U(x) ≤ C_T(x) + c_UT

The machine U is a universal Turing machine. This makes the concept of Kolmogorov complexity invariant up to an additive constant if we put C(x) = C_U(x).

However, it is necessary to understand that this invariance is not absolute because the value of the constant c_UT depends on the choice of the universal Turing machine U (Weinstein, 2003; Burgin, 2005).

It was demonstrated that Kolmogorov complexity cannot be computed by a Turing machine or by any other recursive algorithm (Kolmogorov, 1965) but can be computed by an inductive Turing machine (Burgin, 1982). When the length of a word tends to infinity, its Kolmogorov complexity also tends to infinity.

Diversity of naming, approaches and applications

Although the majority of researchers use Kolmogorov complexity as the standard name for this measure, there are authors who prefer a different name. In particular, the following names of this concept are used: algorithmic information content, algorithmic information, program-size complexity, information content, shortest program length, algorithmic randomness, stochastic complexity, information-theoretic complexity, complexity, randomness, KCS (Kolmogorov-Chaitin-Solomonoff) complexity, information size, and algorithmic entropy.

Different names reflect different approaches to the concept. When we want to know how difficult it might be computing or constructing some object x with recursive algorithms, Kolmogorov or algorithmic complexity is an appropriate name. When the question is how much information we need to build or compute x with given algorithms, the name information size of x better reflects the situation. When we consider probabilistic aspects of x, e.g., randomness, algorithmic entropy might be the best name.

Many versions of Kolmogorov complexity have been introduced. The most known of them are: uniform complexity KR(x), prefix complexity or prefix-free complexity K(x), monotone complexity Km(x), conditional Kolmogorov complexity CD(x), time-bounded Kolmogorov complexity C^t(x), space-bounded Kolmogorov complexity C^s(x), and resource-bounded Kolmogorov complexity C^t,s(x). In addition, Kolmogorov complexity has been extended to infinite processes, infinite words (Chaitin, 1976; 1977), super-recursive algorithms (Burgin, 1995; 2005; Schmidhuber, 2002), quantum computations (Svozil, 1996) and algorithmic problems (Burgin, 2010a).

Existence of different versions of Kolmogorov complexity caused a necessity to build a unified algorithmic information measure. Such a theory has been developed as an axiomatic algorithmic complexity (Burgin, 1982; 1990; 2005; 2010).

References

BURGIN, M. (1982). Generalized Kolmogorov complexity and duality in theory of computations. Soviet Math. Dokl., v.25, No. 3, pp. 19–23
BURGIN, M. (1990). Generalized Kolmogorov Complexity and other Dual Complexity Measures. Cybernetics, No. 4, pp. 21–29
BURGIN, M. (1995). Algorithmic Approach in the Dynamic Theory of Information. Notices of the Russian Academy of Sciences, v. 342, No. 1, pp. 7-10
BURGIN, M. (2005). Super-recursive algorithms, Monographs in computer science, Springer.
BURGIN, M. (2010). Theory of Information: Fundamentality, Diversity and Unification. Singapore: World Scientific Publishing
BURGIN, M. (2010). Algorithmic Complexity of Computational Problems. International Journal of Computing & Information Technology, 2010, v. 2, No. 1, pp. 149-187
CHAITIN, G. J. (1969). “On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers” (PDF). Journal of the ACM, Vol. 16, pp. 407-422.
CHAITIN, G.J. (1976). Information theoretic characterizations of recursive infinite strings. Theoretical Computer Science, v. 2, pp. 45–48
CHAITIN, G.J. (1977). Algorithmic information theory. IBM Journal of Research and Development, v.21, No. 4, pp. 350-359
KOLMOGOROV, A.N. (1965). “Three Approaches to the Quantitative Definition of Information”. Problems Inform. Transmission, Vol. 1, pp. 1–7.
SCHMIDHUBER, J. (2002). Hierarchies of Generalized Kolmogorov Complexities and Nonenumerable Universal Measures Computable in the Limit. International Journal of Foundations of Computer Science, v. 3, No. 4, pp. 587-612
SOLOMONOFF, R. (June 1964). “A Formal Theory of Inductive Inference Part II”. Information and Control 7 (2): 224–254.
SOLOMONOFF, R. (March 1964). “A Formal Theory of Inductive Inference Part I”. Information and Control, Vol. 7, pp. 1–22.
SVOZIL. K. (1996). Quantum Algorithmic Information Theory. Journal of Universal Computer Science, v. 2, pp. 311-346
WEINSTEIN, S. Objectivity, information, and Maxwell's demon, Preprint, PhilSci-Archive, 2003. [Online] <http://philsci-archive.pitt.edu/> [accessed: 14/3/2015]