Elements Of Classical Recursion Theory: Degree-Theoretic Properties And Combinatorial Properties

Abstract

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, a and it also answers an old question by Lerman raised in the 80's. One interesting group of combinatorial properties is the class of tracing notions. They are important in classical recursion theory as well as in algorithmic randomness. We study several different notions of traceability and show that within the n-REA degrees these tracing notions are equivalent to other combinatorial prop- erties. We also introduce a new notion of tree traceability and study some of its properties. We end with a new approach in studying proof-theoretic strength of the totality of recursive functions, and prove several interesting theorems about a degree structure induced by a natural provability reducibility relation on recursive functions.