26 citations · 69 across the 8 of their papers we have counts for
9 papers
Limit complexities revisited [once more]
Laurent Bienvenu, Andrej Muchnik, Alexander Shen +1
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 tha…
Game arguments in computability theory and algorithmic information theory
Andrej Muchnik, Alexander Shen, Mikhail Vyugin
We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap…
Kolmogorov complexity and cryptography
Andrej A. Muchnik
This paper contains some results of An.A.Muchnik (1958-2007) reported in his talks at the Kolmogorov seminar (Moscow State Lomonosov University, Math. Department, Logic and Algorit…
Game interpretation of Kolmogorov complexity
Andrej A. Muchnik, Ilya Mezhirov, Alexander Shen +1
The Kolmogorov complexity function K can be relativized using any oracle A, and most properties of K remain true for relativized versions. In section 1 we provide an explanation fo…
Sequences close to periodic
An. A. Muchnik, Yu. L. Pritykin, A. L. Semenov
The paper is a survey of notions and results related to classical and new generalizations of the notion of a periodic sequence. The topics related to almost periodicity in combinat…
Algorithmic randomness and splitting of supermartingales
Andrej Muchnik
Randomness in the sense of Martin-Löf can be defined in terms of lower semicomputable supermartingales. We show that such a supermartingale cannot be replaced by a pair of supermar…