کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424810 1633467 2014 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Propagation of partial randomness
ترجمه فارسی عنوان
انتشار تصادفی جزئی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 2, February 2014, Pages 742-758
نویسندگان
, , , ,