Limit complexities revisited [once more]

arXiv1204.0201MaRDI QIDQ6232022FDOQ6232022

A. Shen, Nikolai K. Vereshchagin, Laurent Bienvenu, Andrej Muchnik

Publication date: 1 April 2012

Abstract: The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that $limsu{p}_{n}C(x|n)$ equals $C^{0^{\prime }}(x)$. Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary tree, to prove Conidis' theorem about limits of effectively open sets, and also to improve the results of Muchnik about limit frequencies. As a by-product, we get a criterion of 2-randomness proved by Miller: a sequence $X$ is 2-random if and only if there exists $c$ such that any prefix $x$ of $X$ is a prefix of some string $y$ such that $C(y)ge|y|-c$. (In the 1960ies this property was suggested in Kolmogorov as one of possible randomness definitions.) We also get another 2-randomness criterion by Miller and Nies: $X$ is 2-random if and only if $C(x)ge|x|-c$ for some $c$ and infinitely many prefixes $x$ of $X$. This is a modified version of our old paper that contained a weaker (and cumbersome) version of Conidis' result, and the proof used low basis theorem (in quite a strange way). The full version was formulated there as a conjecture. This conjecture was later proved by Conidis. Bruno Bauwens (personal communication) noted that the proof can be obtained also by a simple modification of our original argument, and we reproduce Bauwens' argument with his permission.

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

This page was built for publication: Limit complexities revisited [once more]

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