We show that there are Turing complete computably enumerable sets of arbitrarily low non-trivial initial segment prefix-free complexity. In particular, given any computably enumerable set @math with non-trivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set @math with complexity strictly less than the complexity of @math . 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 @math with non-trivial initial segment prefix-free complexity. An application of this gives a negative answer to a question from [Section 11.12] rodenisbook and MRmerstcdhdtd which asked for minimal pairs in the structure of the c.e. reals ordered by their initial segment prefix-free complexity. Further consequences concern various notions of degrees of randomness. For example, the Solovay degrees and the @math -degrees of computably enumerable reals and computably enumerable sets are not elementarily equivalent. Also, the degrees of randomness based on plain and prefix-free complexity are not elementarily equivalent; the same holds for their @math and @math substructures.
Abstract 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 ≤ L K B , 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 ≤ L K are called L K 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 ≤ L K , given any non-trivial Δ 2 0 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 Σ 1 0 and Δ 2 0 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 0 ″ 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 Δ 2 0 or Σ 1 0 structures of LK degrees. The proofs introduce a new technique of permitting below a Δ 2 0 set that is not K -trivial, which is likely to have wider applications.