کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950614 | 1364294 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Diagonally non-computable functions and fireworks
ترجمه فارسی عنوان
توابع قابل تشخیص و غیر قابل محاسبه و آتش بازی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, the class of coherent completions of Peano Arithmetic or the class of reals of minimal Turing degree. One class of particular interest in the study of negligibility is the class of diagonally non-computable (DNC) functions, proven by KuÄera to be non-negligible in a strong sense: every Martin-Löf random real computes a DNC function. Ambos-Spies et al. showed that the converse does not hold: there are DNC functions which compute no Martin-Löf random real. In this paper, we show that the set of such DNC functions is in fact non-negligible using a technique we call 'fireworks argument'. We also use this technique to prove further results on DNC functions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 1, April 2017, Pages 64-77
Journal: Information and Computation - Volume 253, Part 1, April 2017, Pages 64-77
نویسندگان
Laurent Bienvenu, Ludovic Patey,