کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427530 686517 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Analogues of Chaitinʼs Omega in the computably enumerable sets
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Analogues of Chaitinʼs Omega in the computably enumerable sets
چکیده انگلیسی

We show that there are computably enumerable (c.e.) sets with maximum initial segment Kolmogorov complexity amongst all c.e. sets (with respect to both the plain and the prefix-free version of Kolmogorov complexity). These c.e. sets belong to the weak truth table degree of the halting problem, but not every weak truth table complete c.e. set has maximum initial segment Kolmogorov complexity. Moreover, every c.e. set with maximum initial segment prefix-free complexity is the disjoint union of two c.e. sets with the same property; and is also the disjoint union of two c.e. sets of lesser initial segment complexity.


► There are computably enumerable (c.e.) sets with maximum initial segment Kolmogorov complexity amongst all c.e. sets.
► These complete sets are characterized in the case of one of the measures of initial segment complexity.
► Every c.e. set can be split into two c.e. disjoint parts of the same prefix-free complexity but this fails for plain complexity.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issues 5–6, 15 March 2013, Pages 171–178
نویسندگان
, , , ,