کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436888 690049 2012 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Strong reductions in effective randomness
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Strong reductions in effective randomness
چکیده انگلیسی

We study generalizations of Demuth’s Theorem, which states that the image of a Martin-Löf random real under a tt-reduction is either computable or Turing equivalent to a Martin-Löf random real. We show that Demuth’s Theorem holds for Schnorr randomness and computable randomness (answering a question of Franklin), but that it cannot be strengthened by replacing the Turing equivalence in the statement of the theorem with wtt-equivalence. We also provide some additional results about the Turing and tt-degrees of reals that are random with respect to some computable measure.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 459, 9 November 2012, Pages 55-68