کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662123 1633509 2010 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Elementary differences between the degrees of unsolvability and degrees of compressibility
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Elementary differences between the degrees of unsolvability and degrees of compressibility
چکیده انگلیسی

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies (2005) [14], and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes induced by ≤LK are called LK degrees (or degrees of compressibility) and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies (2005) [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity.We show that with respect to ≤LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 161, Issue 7, April 2010, Pages 923-934