17 citations · 17 across the 2 of their papers we have counts for
2 papers
math.DS2010
A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
Laurent Bienvenu, Adam Day, Mathieu Hoyrup +2
A theorem of Kučera states that given a Martin-Löf random infinite binary sequence ω and an effectively open set A of measure less than 1, some tail of ω is not in A. We first prov…
math.LO2010★ 17 cited
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…