Loading...
Please wait, while we are loading the content...
Similar Documents
Descriptive Complexity of Computable Sequences Revisited
| Content Provider | arXiv |
|---|---|
| Author | Vereshchagin, Nikolay |
| Date of Submission | 2019-02-04 |
| 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'}(\alpha )$, defined as the minimal length of a program with oracle $0'$ that prints $\alpha$, and $M_{\infty}(\alpha)$, defined as $\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'}(\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. |
| Related Links | https://arxiv.org/pdf/1902.01279.pdf |
| arXiv | 1902.01279 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Logic Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
