Super-recursive Kolmogorov complexity

Mark Burgin (2016). Super-recursive Kolmogorov complexity, GlossariumBITri, 2(1): 10.

Collection	GlossariumBITri
Author	Mark Burgin
Editor	Mark Burgin
Year	2016
Vol. (num.)	2(1)
ID	◀ 10 ▶
Object type	Concept
Domain	Coding Theory, Complexity Theory, Computer Science, Algorithmic Information Theory
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 (s. Kolmogorov Complexity). If $x$ is a word and $\mathit{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 $C_B(x)$ of an object (word) $x$ with respect to an algorithm $B$ from $\mathit{K}$ is defined as:

$C_B(x):=\{\begin{array}{ll}\min \{l(p)\mid B(p)=x\},& \text{if}\mathrm{\exists }\text{a word}p\mid B(p)=x\\ \text{undefined},& \text{otherwise}\end{array}$(1)

where $l(p)$ is the length of the word $p$.

When $\mathit{K}$ has universal algorithms, Burgin (1982; 2005) proved that there is an invariant up to some additive constant super-recursive Kolmogorov complexity $\mathit{K}C(x)$. It is called absolute super-recursive Kolmogorov complexity because there is also relative super-recursive Kolmogorov complexity $\mathit{K}C(x)$. Namely, there is an algorithm $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)\le C_T(x)+c_{UT}$(2)

The machine $U$ is a universal in $\mathit{K}$ algorithm. This makes the concept of super-recursive Kolmogorov complexity invariant up to an additive constant if we put $\mathit{K}C(x)$ $=C_U(x)$

Thus, the super-recursive Kolmogorov complexity $\mathit{K}C(x)$ of a word $x$ is taken to be equal to:

$\mathit{K}C(x):=\{\begin{array}{l}\text{the size of the shortest program (in number of symbols)}\\ \text{for a universal in}\mathit{K}\text{algorithm}U\\ \text{that without additional data, computes the string}x\text{and terminates.}\end{array}$(3)

This measure is called absolute super-recursive Kolmogorov complexity because super-recursive Kolmogorov complexity has also a relative form $\mathit{K}C(x\mid 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.

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:

$IC(x):=\{\begin{array}{l}\text{the size of the shortest program (in number of symbols)}\\ \text{for a universal inductive Turing machine of the first order}U\\ \text{that without additional data, computes the string}x.\end{array}$(4)

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\mid 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\mid y)$ allows one to find the algorithmic quantity $IC(x\mid y)$ 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(x\mid y)=C(x)-C(x\mid y)$(5)

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

$I{C}_T(x):=\{\begin{array}{ll}\min \{l(p)\mid T(p)=x\},& \text{if}\mathrm{\exists }\text{a word}p\mid T(p)=x\\ \text{undefined},& \text{otherwise}\end{array}$(6)

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 $c_T$ such that for all words $x$, we have:

$I{C}_U(x)\le I{C}_T(x)+c_T$(7)

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.