کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434763 | 689795 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Process and truth-table characterisations of randomness
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper uses quick process machines to provide characterisations of computable randomness, Schnorr randomness and weak randomness. The quick process machine is a type of process machine first considered in work of Levin and Zvonkin. A new technique for building process machines and quick process machines is presented. This technique is similar to the KC theorem for prefix-free machines. Using this technique, a method of translating computable martingales to quick process machines is given. This translation forms the basis for these new randomness characterisations. Quick process machines are also used to provide characterisations of computable randomness, Schnorr randomness, and weak randomness in terms of truth-table reducibility.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 452, 21 September 2012, Pages 47-55
Journal: Theoretical Computer Science - Volume 452, 21 September 2012, Pages 47-55