When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1335
URN: urn:nbn:de:0030-drops-13350
Go to the corresponding LIPIcs Volume Portal

Bienvenu, Laurent ; Muchnik, Andrej ; Shen, Alexander ; Veraschagin, Nikolay

Limit complexities revisited

22011.BienvenuLaurent.Paper.1335.pdf (0.2 MB)


The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional (plain) Kolmogorov complexity of $x$ when $n$ is known) equals $KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with $mathbf{0'$-oracle. Then we use the same argument to prove similar results for prefix complexity (and also improve results of (Muchnik, 1987) about limit frequencies), a priori probability on binary tree and measure of effectively open sets. As a by-product, we get a criterion of $mathbf{0'$ Martin-L"of randomness (called also $2$-randomness) proved in (Miller, 2004): a sequence $omega$ is $2$-random if and only if there exists $c$ such that any prefix $x$ of $omega$ is a prefix of some string $y$ such that $KS(y)ge |y|-c$. (In the 1960ies this property was suggested in (Kolmogorov, 1968) as one of possible randomness definitions; its equivalence to $2$-randomness was shown in (Miller, 2004) while proving another $2$-randomness criterion (see also (Nies et al. 2005)): $omega$ is $2$-random if and only if $KS(x)ge |x|-c$ for some $c$ and infinitely many prefixes $x$ of $omega$. Finally, we show that the low-basis theorem can be used to get alternative proofs for these results and to improve the result about effectively open sets; this stronger version implies the $2$-randomness criterion mentioned in the previous sentence.

BibTeX - Entry

  author =	{Laurent Bienvenu and Andrej Muchnik and Alexander Shen and Nikolay Veraschagin},
  title =	{{Limit complexities revisited}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{73--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-13350},
  doi =		{},
  annote =	{Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis}

Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI