Bienvenu, Laurent ;
Muchnik, Andrej ;
Shen, Alexander ;
Veraschagin, Nikolay
Limit complexities revisited
Abstract
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(xn)$ (here $KS(xn)$ 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 byproduct, we get a criterion of
$mathbf{0'$ MartinL"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 yc$. (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 xc$ for some $c$ and infinitely many
prefixes $x$ of $omega$.
Finally, we show that the lowbasis 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
@InProceedings{bienvenu_et_al:LIPIcs:2008:1335,
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 = {7384},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1335},
URN = {urn:nbn:de:0030drops13350},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1335},
annote = {Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2randomness, low basis}
}
Keywords: 

Kolmogorov complexity, limit complexities, limit frequencies, 2randomness, low basis 
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2008 
Date of publication: 

06.02.2008 