Descriptive Complexity of Computable Sequences Revisited

Abstract

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^{\prime }}(\alpha )$, defined as the minimal length of a program with oracle $0^{\prime }$ that prints $\alpha$, and $M_{\infty }(\alpha )$, defined as $\mathrm{liminf}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^{\prime }}(\alpha )\le M_{\infty }(\alpha )+O(1)$ and $M_{\infty }(\alpha )$ is not bounded by any computable function of $C^{0^{\prime }}(\alpha )$, even on the domain of computable sequences.