Solovay functions and their applications in algorithmic randomness

• We introduce the notion of Solovay function, as a type of ‘good approximation of Kolmogorov complexity’.
• We show that most of the classical theory of algorithmic randomness can be rebuilt based on Solovay functions.
• Likewise, we show that Solovay functions integrate nicely in the study of K-triviality.

Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions f≥K+O(1)f≥K+O(1) such that for infinitely many strings σ  , f(σ)=K(σ)+O(1)f(σ)=K(σ)+O(1), where K denotes prefix-free Kolmogorov complexity. Such an f is now called a Solovay function. We prove that many classical results about K can be obtained by replacing K by a Solovay function. For example, the three following properties of a function g all hold for the function K.(i)The sum of the terms ∑n2−g(n)∑n2−g(n) is a Martin-Löf random real.(ii)A sequence A is Martin-Löf random if and only if g(A↾n)>n−O(1)g(A↾n)>n−O(1).(iii)A sequence A is K-trivial if and only if K(A↾n)