کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426014 | 685981 | 2013 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Universal computably enumerable sets and initial segment prefix-free complexity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show that there are Turing complete computably enumerable sets of arbitrarily low nontrivial initial segment prefix-free complexity. In particular, given any computably enumerable set A with nontrivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set B with complexity strictly less than the complexity of A. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete.Moreover we give a generalization of this result for any finite collection of computably enumerable sets AiAi, i
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 233, December 2013, Pages 41–59
Journal: Information and Computation - Volume 233, December 2013, Pages 41–59
نویسندگان
George Barmpalias,