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

Kolmogorov complexitylimit complexitycomputable sequences

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• 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
• 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

(5)

• Descriptive complexity of \#P functions: a new perspective
• DESCRIPTIVE COMPLEXITY IN CANTOR SERIES
• Resolute sequences in initial segment complexity
• Descriptive complexity of computable sequences
• On the complexity of computable real 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)