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 $f>K+O(1)$ such that for infinitely many st…