2 papers
math.LO2016
Solovay functions and their applications in algorithmic randomness
Laurent Bienvenu, Rod Downey, Wolfgang Merkle +1
Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions such that for infinitely many st…
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…