کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424810 | 1633467 | 2014 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Propagation of partial randomness
ترجمه فارسی عنوان
انتشار تصادفی جزئی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
چکیده انگلیسی
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
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 2, February 2014, Pages 742-758
نویسندگان
Kojiro Higuchi, W.M. Phillip Hudelson, Stephen G. Simpson, Keita Yokoyama,