Super-Recursive Kolmogorov Complexity
| Collection | GlossariumBITri |
|---|---|
| Author | Mark Burgin |
| Editor | Mark Burgin |
| Year | 2016 |
| Volume | 2 |
| Number | 1 |
| ID | 10 |
| Object type | Concept |
| Domain | Ait Coding Theory Complexity Theory Computer Science |
| es | complejidad de Kolmogorov super-recursiva |
| fr | Complexité de Kolmogorov super-récursif |
| de | Superrekursive Kolmogorow-Komplexität |
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){{{1}}}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). 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 x 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(x ).
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.
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 x 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(x ). Namely, the relative inductive Kolmogorov complexity IC(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 inductive Turing machine U that with y as its input, computes the string x and terminates.
The inductive relative Kolmogorov complexity IC(x ) allows one to find the algorithmic quantity IC(y ; x) of inductive information in a word y about a word x, i.e., information that can be extracted by inductive algorithms. Namely, we have
IC(y ; x) = C(x) - C(x )
The inductive Kolmogorov complexity of an object (word) x with respect to an inductive Turing machine T is defined as
ICT(x){{{1}}}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.
References
- BURGIN, M. (1982). Generalized Kolmogorov complexity and duality in theory of computations. Soviet Math. Dokl., Vol. 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, Heidelberg: Springer.