The proof of Levin's conjecture (Q1263857)

This paper deals with the proof of Levin's conjecture and its generalization to the case where the probability distribution is not assumed computable. In the introduction the Levin's conjecture is restated for any finite alphabet ergodic stationary stochastic process with computable probability distribution. In the next section three theorems are given. Theorem 1 states several inequalities among the Kolmogorov complexity and conditional Kolmogorov complexity. These inequalities can be proved be definition of complexities and by constructing partial recursive functions. Based on this theorem a corollary is given which is useful for the proof of the next two theorems. So Levin's conjecture is the immediate consequence of Theorems 2 and 3. The author concludes that the Levin's conjecture is also valid in the multidimensional complexity case. This paper contains clear and efficient demonstrations which can be used for teaching purposes.