کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434779 689799 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lowness for bounded randomness
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Lowness for bounded randomness
چکیده انگلیسی

In [3], Brodhead, Downey and Ng introduced some new variations of the notions of being Martin-Löf random where the tests are all clopen sets. We explore the lowness notions associated with these randomness notions. While these bounded notions seem far from classical notions with infinite tests like Martin-Löf and Demuth randomness, the lowness notions associated with bounded randomness turn out to be intertwined with the lowness notions for these two concepts. In fact, in one case, we get a new and likely very useful characterization of K-triviality.

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