کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4609141 1338414 2006 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Random non-cupping revisited
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
پیش نمایش صفحه اول مقاله
Random non-cupping revisited
چکیده انگلیسی

Say that Y has the strong random anticupping property if there is a set A such that for every Martin–Löf random set RY⩽TA⊕R⇒Y⩽TRY⩽TA⊕R⇒Y⩽TR(in this case A is an anticupping witness for Y  ). Nies has shown that every random Δ20 set has the strong random anticupping property via a promptly simple anticupping witness. We show that every Δ20 set has the random anticupping property via a promptly simple anticupping witness. Moreover, we prove the following stronger statement: for every non-computable Y⩽T∅′Y⩽T∅′ there exists a promptly simple A such thatY⩽TA⊕R⇒A⩽TRY⩽TA⊕R⇒A⩽TRfor all Martin–Löf random sets R.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 22, Issue 6, December 2006, Pages 850–857
نویسندگان
,