Kolmogorov complexity of initial segments of sequences and arithmetical definability

摘要

The structure of the K-degrees provides a way to classify sets of natural numbers or infinite binary sequences with respect to the level of randomness of their initial segments. In the K-degrees of infinite binary sequences, X is below Y if the prefix-free Kolmogorov complexity of the first n bits of X is less than the complexity of the first n bits of Y, for each n. Identifying infinite binary sequences with subsets of N, we study the K-degrees of arithmetical sets and explore the interactions between arithmetical definability and prefix-free Kolmogorov complexity. We show that in the K-degrees, for each n > 1, there exists a ∑_n~0 non-zero degree which does not bound any Δ_n~0 non-zero degree. An application of this result is that in the K-degrees there exists a ∑_2~0 degree which forms a minimal pair with all ∑_1~0 degrees. This extends the work of Csima and Montalban (2006) [8] and Merkle and Stephan (2007) [17]. Our main result is that, given any Δ_2~0 family C of sequences, there is a Δ_2~0 sequence of non-trivial initial segment complexity which is not larger than the initial segment complexity of any non-trivial member of C. This general theorem has the following surprising consequence. There is a 0'-computable sequence of non-trivial initial segment complexity, which is not larger than the initial segment complexity of any non-trivial computably enumerable set. Our analysis and results demonstrate that, examining the extend to which arithmetical definability interacts with the K reducibility (and in general any 'weak reducibility') is a fruitful way of studying the induced structure.