76 citations · 76 across the 3 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009
Separations of non-monotonic randomness notions
Laurent Bienvenu, Rupert Hoelzl, Thorsten Kraling +1
In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Mart…
math.LO2009★ 76 cited
Kolmogorov complexity and the Recursion Theorem
Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan
Several classes of DNR functions are characterized in terms of Kolmogorov complexity. In particular, a set of natural numbers A can wtt-compute a DNR function iff there is a nontri…