Descriptive complexity of computable sequences revisited (Q2290652): Difference between revisions

Consider the following two complexities of an infinite computable binary sequence \(\alpha\): \(C^{0'}(\alpha)\) is the minimal length of a program with oracle \(0'\) that prints \(\alpha\), and \(M_{\infty}(\alpha)\) is \(\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. The paper proves the following two results: \(C^{0'}(\alpha)\le M_{\infty}(\alpha)+O(1)\) and \(M_{\infty}(\alpha)\) is not bounded by any computable function of \(C^{0'}(\alpha)\), even on the domain of computable sequences. They answer two questions left open in [\textit{B. Durand} et al., Theor. Comput. Sci. 271, No. 1--2, 47--58 (2002; Zbl 0982.68074)].