On C-degrees, H-degrees and T-degrees

Abstract

Following a line of research that aims at relating the computation power and the initial segment complexity of a set, the work presented here investigates into the relations between Turing reducibility, defined in terms of computation power, and C-reducibility and H-reducibility, defined in terms of the complexity of initial segments. The global structures of all C-degrees and of all H-degrees are rich and allows to embed the lattice of the power set of the natural numbers under inclusion. In particular, there are C-degrees, as well as H-degrees, that are different from the least degree and are the meet of two other degrees, whereas on the other hand there are pairs of sets that have a meet neither in the C-degrees nor in the H-degrees; these results answer questions in a survey by Nies and Miller. There are r.e. sets that form a minimal pair for C-reducibility and ∑2 0 sets that form a minimal pair for H-reducibility, which answers questions by Downey and Hirschfeldt. Furthermore, the following facts on the relation between C-degrees, H-degrees and Turing degrees hold. Every C-degree contains at most one Turing degree and this bound is sharp since there are C-degrees that do contain a Turing degree. For the comprising class of complex sets, neither the C-degree nor the H-degree of such a set can contain a Turing degree, in fact, the Turing degree of any complex set contains infinitely many C-degrees. Similarly the Turing degree of any set that computes the halting problem contains infinitely many H-degrees, while the H-degree of any 2-random set R is never contained in the Turing degree of R. By the latter, H-equivalence of Martin-Löf random sets does not imply their Turing equivalence. The structure of the C-degrees contained in the Turing degree of a complex sets is rich and allows to embed any countable distributive lattice; a corresponding statement is true for the structure of H-degrees that are contained in the Turing degree of a set that computes the halting problem. © 2007 IEEE.