ELEMENTS OF CLASSICAL RECURSION THEORY: DEGREE-THEORETIC PROPERTIES AND COMBINATORIAL PROPERTIES
Mingzhong Cai · eCommons (Cornell University) · 2011
In Recursion Theory (Computability Theory), we study Turing degrees in terms of their degree-theoretic properties and combinatorial properties. In this dissertation we present several results in terms of connections either between these two categories of properties or within each category. Our first main result is to build a strong connection between array nonrecursive degrees and relatively recursively enumerable degrees. The former is a combinatorial property and the latter is a degree-theoretic one. We prove that a degree is array nonrecursive if and only if every degree above it is relatively recursively enumerable. This result has a corollary which generalizes Ishmukhametov’s classification of r.e. degrees with strong minimal covers to the class of n-REA degrees. Then we produce new connections between minimality and jump classes, both are degree-theoretic. By using more and more complicated structures, we can finally build a minimal cover over a minimal degree (which we call a 2-minimal degree) which is GH1, and this is the highest jump class we can reach by finite iterations of minimality. This result answers a question by Lewis and Montalbán,