Analogues of Chaitin's Omega in the computably enumerable sets

Analogues of Chaitin's Omega in the computably enumerable sets

0.00 Avg rating0 Votes
Article ID: iaor20131575
Volume: 113
Issue: 5-6
Start Page Number: 171
End Page Number: 178
Publication Date: Mar 2013
Journal: Information Processing Letters
Authors: , , ,
Keywords: computers: calculation
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.