Mingzhong Cai
Mingzhong Cai

Ph.D. (2011) Cornell University

First Position
Dissertation
Advisor:
Research Area:
Abstract: In recursion theory (computability theory), we study Turing degrees in terms of their degreetheoretic 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 degreetheoretic 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 nREA degrees.
Then we produce new connections between minimality and jump classes, both are degreetheoretic. By using more and more complicated structures, we can finally build a minimal cover over a minimal degree (which we call a 2minimal degree) which is GH_{1}, 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, 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 nREA degrees these tracing notions are equivalent to other combinatorial properties. We also introduce a new notion of tree traceability and study some of its properties.
We end with a new approach in studying prooftheoretic 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.