Limit complexities revisited [once more]

2012. No. 1204.0201.

Bienvenu L., Muchnik A., Shen A., Vereshchagin N.

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 lim supnC(x|n) equals C0′(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)≥|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)≥|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.

Keywords: Kolmogorov complexity, limit complexity