20 citations · 68 across the 15 of their papers we have counts for
5 papers · 1 filter
Conditional probabilities and van Lambalgen theorem revisited
Bruno Bauwens, Alexander Shen, Hayato Takahashi
The definition of conditional probability in case of continuous distributions was an important step in the development of mathematical theory of probabilities. How can we define th…
Layerwise computability and image randomness
Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object shoul…
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…
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…