کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429511 687592 2015 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solovay functions and their applications in algorithmic randomness
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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)

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 81, Issue 8, December 2015, Pages 1575–1591
نویسندگان
, , , ,