کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952152 | 1442014 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Kobayashi compressibility
ترجمه فارسی عنوان
فشرده سازی کابایاشی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کوبایاشی، فشرده سازی، تصادفی بودن، پیچیدگی کلموگروف، کاهش یکنواخت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that Kobayashi compressibility can be used in order to define Martin-Löf randomness, a strong version of finite randomness and Kurtz randomness, strictly in terms of Turing reductions. Moreover these randomness notions naturally correspond to Turing reducibility, weak truth-table reducibility and truth-table reducibility respectively. Finally we discuss Kobayashi's main result from [21] regarding the compressibility of computably enumerable sets, and provide additional related original results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 675, 2 May 2017, Pages 89-100
Journal: Theoretical Computer Science - Volume 675, 2 May 2017, Pages 89-100
نویسندگان
George Barmpalias, Rodney G. Downey,