کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6873900 1440711 2018 29 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Schnorr randomness for noncomputable measures
ترجمه فارسی عنوان
تصادف شونور برای اقدامات غیرقابل حل
کلمات کلیدی
تصادف الگوریتمی، تصادف شونور، تست یکپارچه یکنواخت، اقدامات غیرقابل حل،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper explores a novel definition of Schnorr randomness for noncomputable measures. We say x is uniformly Schnorr μ-random if t(μ,x)<∞ for all lower semicomputable functions t(μ,x) such that μ↦∫t(μ,x)dμ(x) is computable. We prove a number of theorems demonstrating that this is the correct definition which enjoys many of the same properties as Martin-Löf randomness for noncomputable measures. Nonetheless, a number of our proofs significantly differ from the Martin-Löf case, requiring new ideas from computable analysis.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 258, February 2018, Pages 50-78
نویسندگان
,