Descriptive complexity of computable sequences revisited

DOI10.1016/J.TCS.2020.01.013MaRDI QIDQ2290652zbMATH OpenOpenAlexWikidataFDO

Authors Nikolai K. Vereshchagin

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.01279

zbMATH Keywords

computable sequencesKolmogorov complexitylimit complexity

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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 $liminfC(alph{a}_{1:n}|n)$, where $alph{a}_{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.

Review text

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)].

Recommendations

• Descriptive complexity of computable sequences
• scientific article; zbMATH DE number 1304316
• Logical Approaches to Computational Barriers
• On minimal-program complexity measures
• Kolmogorov-Complexity Based on Infinite Computations

Cites work

• A formal theory of inductive inference. Part II
• A variant of the Kolmogorov concept of complexity
• Classical recursion theory. Vol. II
• Descriptive complexity of computable sequences
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Kolmogorov Complexity and Algorithmic Randomness
• Kolmogorov complexity conditional to large integers
• On the Length of Programs for Computing Finite Binary Sequences
• Relations between varieties of kolmogorov complexities

Cited in

(6)

• Descriptive complexity of \#P functions: a new perspective
• On the complexity of computable real sequences
• scientific article; zbMATH DE number 1304316 (Why is no real title available?)
• DESCRIPTIVE COMPLEXITY IN CANTOR SERIES
• Resolute sequences in initial segment complexity
• Descriptive complexity of computable sequences

This page was built for publication: Descriptive complexity of computable sequences revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290652)