کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429511 | 687592 | 2015 | 17 صفحه PDF | دانلود رایگان |
• 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)
Journal: Journal of Computer and System Sciences - Volume 81, Issue 8, December 2015, Pages 1575–1591