Research Interests

I am currently interested in classical Recursion Theory. For these who are not logicians, it is the study of the complexity of a set or a function in the sense of effective/recursive deduction (just for a very easy example, any set A and its complement are recursive in each other, as we can effectively tell whether a number x is in A by asking its complement and reverse the answer). Classical Recursion Theory focuses on the study of Turing degrees, i.e., the partial order of sets of natural numbers modulo the effective deduction equivalence. We are trying to investigate how "powerful" a set is in various computability ways, for example, based on what sets we can effectively solve the halting problem, or equivalently tell whether a Diophantine equation has an integer solution.

For logicians, I have done some research on array nonrecursive (ANR) and array recursive (AR) degrees, minimal degrees and minimal covers, generalized high/low hierarchy and some interesting relations between these subjects. Most of these topics are related to a general question of what it means that a degree is low, or "unpowerful", and that a degree is high, or "powerful", in terms of computability power. For example, the minimal degrees are intuitively very low, as they are just "one step" from the recursive degree 0. Some of my research shows that within "two steps" one can actually get some "powerful" degrees like the ANR ones.

In addition, I am also very interested in fast growing recursive functions and related topics on their independence with respect to common axioms systems like Peano Arithmetic.

Publications and Preprints

Research partially supported by NSF Grants DMS-0554855 and DMS-0852811.
  • Three theorems on $n$-REA degrees: proof-readers and verifiers
    to appear in Computability in Europe 2011 (original version will appear at www.springerlink.com)
  • The n-r.e. degrees: undecidability and $\Sigma_1$ substructures
    submitted (with Theodore A. Slaman and Richard A. Shore)
  • A 2-minimal non-$GL_2$ degree
    to appear in the Journal of Mathematical Logic
  • A hyperimmune minimal degree and an ANR 2-minimal degree
    Notre Dame Journal of Formal Logic, Volume 51, Number 4, 2010, Pages 443-455
  • Array nonrecursiveness and relative recursive enumerability
    to appear in the Journal of Symbolic Logic
  • Domination, forcing, array nonrecursiveness and relative recursive enumerability
    to appear in the Journal of Symbolic Logic (with Richard A. Shore)

    • BACK