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 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 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
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 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. 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 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. 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
| Entries
New entry. For doing a new entry: (1) the user must be identified as an authorized user(to this end, the "sign in" link 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] |
Glossary (en) >
