Descriptive complexity of computable sequences revisited

Theoretical Computer Science. 2020. Vol. 809. P. 531–537.

Vereshchagin N.

  The purpose of this paper is   to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58].   Namely, we consider   the following two   complexities of an infinite computable 0-1-sequence $\alpha$:   $C^{0'}(\alpha )$, defined as   the minimal length of a program with oracle $0'$ that prints   $\alpha$,   and  $\MM(\alpha)$,  defined as $\limsup C(\alpha_{1:n}|n)$, where   $\alpha_{1:n}$ denotes the length-$n$ prefix of $\alpha$   and $C(x|y)$ stands for conditional Kolmogorov complexity.   We show that $C^{0'}(\alpha )\le \MM(\alpha)+O(1)$ and   $\MM(\alpha)$ is not bounded by any computable function of $C^{0'}(\alpha )$,   even   on the domain of computable sequences.

Keywords: колмогоровская сложность, Kolmogorov complexity, limit complexity, computable sequence, вычислимая последовательность, предельная сложность

Publication based on the results of: Mathematical methods in computational complexity theory and algorithm game theory (2020)