کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661790 | 1633469 | 2013 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Kolmogorov complexity and computably enumerable sets
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Kolmogorov complexity and computably enumerable sets Kolmogorov complexity and computably enumerable sets](/preview/png/4661790.png)
چکیده انگلیسی
We present an extended discussion of the existing research on this topic, along with recent developments and open problems. Besides this survey, our main original result is the following characterization of the computably enumerable sets with trivial initial segment prefix-free complexity. A computably enumerable set A is K-trivial if and only if the family of sets with complexity bounded by the complexity of A is uniformly computable from the halting problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 164, Issue 12, December 2013, Pages 1187-1200
Journal: Annals of Pure and Applied Logic - Volume 164, Issue 12, December 2013, Pages 1187-1200
نویسندگان
George Barmpalias, Angsheng Li,