کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
424418 | 685443 | 2007 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Schnorr Trivial Reals: A construction
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in [11] that all K-trivial reals are low. In this paper, we prove that if h is a high degree, then every degree a⩾Th contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 167, 24 January 2007, Pages 79-93
Journal: Electronic Notes in Theoretical Computer Science - Volume 167, 24 January 2007, Pages 79-93