کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426014 685981 2013 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Universal computably enumerable sets and initial segment prefix-free complexity
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Universal computably enumerable sets and initial segment prefix-free complexity
چکیده انگلیسی

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
نویسندگان
,