کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952152 1442014 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kobayashi compressibility
ترجمه فارسی عنوان
فشرده سازی کابایاشی
کلمات کلیدی
کوبایاشی، فشرده سازی، تصادفی بودن، پیچیدگی کلموگروف، کاهش یکنواخت،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,