Limit complexities revisited [once more]

Details Limit complexities revisited [once more] Limit complexities revisited [once more]

2012-04-01

arxiv.org/abs/1204.0201v1

Mathematics

Logic

See http://arxiv.org/abs/0802.2833 for the old paper

Scientific paper

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 $\limsup_n C(x|n)$ equals $C^{0'}(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.

Affiliated with

Also associated with

No associations

Rating

Limit complexities revisited [once more] does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Limit complexities revisited [once more], we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Limit complexities revisited [once more] will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552453