×

A random degree with strong minimal cover. (English) Zbl 1152.03034

This paper is concerned with the fundamental issue of the relationship between Turing complexity and randomness; in particular, the Turing degrees of Martin-Löf random sets. The main theorem of the paper shows that there exists a Martin-Löf random degree which has a strong minimal cover, where a (Turing) degree is called Martin-Löf random if it contains a set which is Martin-Löf random, and a degree b is called a strong minimal cover of a degree a if the degrees strictly below b are precisely the degrees below and including a. This theorem provides a negative answer to the question: Do all Martin-Löf random degrees satisfy the cupping property? (A degree a satisfies the cupping property if for every \({\mathbf b}>{\mathbf a}\) there exists \({\mathbf c}<{\mathbf b}\) with \({\mathbf b}={\mathbf a}\vee {\mathbf c}\).) The proof of the main theorem is based on a forcing argument. Combining this argument with the standard technique for constructing hyperimmune-free degrees, the author further shows that there exists a hyperimmune-free degree which is random and which has a strong minimal cover. In particular, the hyperimmune-free degrees with strong minimal cover cannot be characterized as those which are not FPF (fixed-point free).

MSC:

03D28 Other Turing degree structures
03D80 Applications of computability and recursion theory
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI