• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Descriptive complexity of computable sequences revisited

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

  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.