Glossary (en)‎ > ‎

Super-recursive Kolmogorov complexity

Version española  (non-available yet)
Incorporated contributions
Burgin (17/02/2011)
Usage domain
AIT, computer science, complexity theory, coding theory
Complexité de Kolmogorov super-récursif
German Super-rekursive Kolmogorow-Komplexität 
Contents1) Absolute and relative super-recursive complexity; 2) Inductive Kolmogorov complexity

1. Absolute and relative super-recursive complexity

Super-recursive 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 and K is a class of super-recursive algorithms, then, as in the case of recursive algorithms, we have two types of super-recursive Kolmogorov complexity.

The Kolmogorov complexity CB(x) of an object (word) x with respect to an algorithm B from K is defined as

CB(x) = min {l(p);  B(p) = x}

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

otherwise CB(x) is not defined.

When K has universal algorithms, Burgin (1982; 2005) proved that there is an invariant up to some additive constant super-recursive Kolmogorov complexity KC(x). It is called absolute super-recursive Kolmogorov complexity because there is also relative super-recursive Kolmogorov complexity KC(x|y). Namely, there is an algorithm 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 in K algorithm. This makes the concept of super-recursive Kolmogorov complexity invariant up to an additive constant if we put KC(x) = CU(x).

Thus, the super-recursive Kolmogorov complexity KC(x) of a word is taken to be equal to:

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

This measure is called absolute super-recursive Kolmogorov complexity because super-recursive Kolmogorov complexity has also a relative form KC(y).

There are many different classes of super-recursive algorithms: limiting recursive functions and limiting partial recursive functions introduced by Gold, trial and error predicates introduced by Hilary Putnam, inductive Turing machines of different orders and limit Turing machines of different orders introduced by Burgin, trial-and-error machines introduced by Hintikka and Mutanen, general Turing machines introduced by Schmidhuber, etc. Each of these classes defines its own super-recursive Kolmogorov complexity.

2. Inductive Kolmogorov Complexity

Inductive Turing machines form the class of super-recursive algorithms closest to the conventional classes of algorithms, such as the class of all Turing machines. As a result, the closest to the conventional (recursive) Kolmogorov complexity C(x) is inductive Kolmogorov complexity IC(x). If x is a word, then the original Kolmogorov complexity IC(x) of a word is taken to be equal to

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

This measure is called absolute inductive Kolmogorov complexity because inductive Kolmogorov complexity has also a relative form IC(y). Namely, the relative inductive Kolmogorov complexity IC(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 inductive Turing machine U that with y as its input, computes the string x and terminates.

The inductive relative Kolmogorov complexity IC(x | y) allows one to find the algorithmic quantity IC(y ; x) of inductive information in a word about a word x, i.e., information that can be extracted by inductive algorithms. Namely, we have

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

The inductive Kolmogorov complexity of an object (word) x with respect to an inductive Turing machine T is defined as

ICT(x) = min { l(p);  T(p) = x}

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

otherwise ICT(x) is not defined.

Burgin (1990; 1995) proved that there is an invariant inductive Kolmogorov complexity IC(x). Namely, there is an inductive Turing machine U such that for any inductive Turing machine T, there is a constant cT such that for all words x, we have

ICU(x£ ICT(x) + cT

The machine U is a universal inductive Turing machine. This makes the concept of inductive Kolmogorov complexity invariant up to an additive constant.

It is proved (Burgin, 2005) that inductive Kolmogorov complexity for a word x is usually much less than recursive (conventional) Kolmogorov complexity for the same word. It means that to build a constructive object, e.g., a word, it is necessary to have much less inductive algorithmic information than recursive algorithmic information.

At the same time, many properties of inductive Kolmogorov complexity are similar to the properties of the conventional Kolmogorov complexity For instance, when the length of a word tends to infinity, its inductive Kolmogorov complexity also tends to infinity.

  • 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.
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.

Burgin (17/02/2011)

[After review, the article was moved to the article column on 16/12/2011]