Descriptive complexity of computable sequences revisited

DOI10.1016/J.TCS.2020.01.013zbMATH Open1443.68075arXiv1902.01279OpenAlexW3000495224WikidataQ126347941 ScholiaQ126347941MaRDI QIDQ2290652FDOQ2290652

Authors: Nikolai K. Vereshchagin 

Publication date: 29 January 2020

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

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.

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

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

zbMATH Keywords

Kolmogorov complexitylimit complexitycomputable sequences

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part II
• Kolmogorov Complexity and Algorithmic Randomness
• A variant of the Kolmogorov concept of complexity
• Classical recursion theory. Vol. II
• Relations between varieties of kolmogorov complexities
• Kolmogorov complexity conditional to large integers
• Descriptive complexity of computable sequences

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)