Glossary (en)‎ > ‎

### Kolmogorov complexity

 Editor Burgin, Markmarkburg@cs.ucla.edu Incorporated contributions Burgin (17/2/2011) Usage domain AIT, computer science, complexity theory, coding theory Type concept French Complexité de Kolmogorov German Kolmogorow-Komplexität

Contents: 1) Absolute and relative complexity measures; 2) Complexity with respect to an algorithm; 3) Absolute Kolmogorov complexity; 4) Diversity of naming, approaches and applications.

1. 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 (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(y). Namely, the relative Kolmogorov complexity C(x | y) of the word relative to the word 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)

2. Complexity with respect to an algorithm

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

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

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

otherwise CA(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.

3. 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 cUT such that for all words x, we have

CU(x£ CT(x) + cUT

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) = CU(x).

However, it is necessary to understand that this invariance is not absolute because the value of the constant cUT depends on the choice of the universal Turing machine (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.

4. 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 contentalgorithmic informationprogram-size complexityinformation contentshortest program lengthalgorithmic randomnessstochastic complexityinformation-theoretic complexitycomplexity, randomnessKCS (Kolmogorov-Chaitin-Solomonoff) complexityinformation 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.

Kolmogorov, or algorithmic, complexity has become an important and popular tool in computer science, programming, probability theory, statistics, and information theory. It has found applications in medicine, biology, neurophisiology, physics, economics, hardware and software engineering. For instance, in physics, problems of quantum gravity are analyzed based on algorithmic complexity of the given object, algorithmic complexity is applied to quantum mechanics, chaotic dynamics, thermodynamics, mechanics and symbolic dynamical systems.

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 Ct(x), space-bounded Kolmogorov complexity Cs(x), and resource-bounded Kolmogorov complexity Ct,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 UnificationSingapore: 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 16: 407.
• 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 1 (1): 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 7 (1): 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)
Entries
New entry. For doing a new entry: (1) the user must be identified as an authorized user(to this end, the "sign inlink at the page bottom left can be followed). (2) After being identified, press the "edit page" button at he upper right corner. (3) Being in edition mode, substitute -under this blue paragraph- "name" by the authors' names, "date" by the date in which the text is entered; and the following line by the proposed text. At the bottom of the entry, the references -used in the proposed text- must be given using the normalized format. (4) To finish, press the "save" button at the upper right corner.
The entry will be reviewed by the editor and -at least- another peer, and subsequently articulated in the article if elected.

Name (dd/mm/yyyy)

[To be substituted by the author with the proposed text]

Incorporated entries

Whenever an entry is integrated in the article (left column) the corresponding entry is reflected in this section.

Mark Burgin (17/2/2011)

[The entry was moved to the article column after review on 16/12/2011]