Back to search

Cornell University

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

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cai, Mingzhong
Chair dc:contributor.chair
  • Shore, Richard A
Committee members dc:contributor.committeemember
  • Moore, Justin Tatch
  • Nerode, Anil

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7955498

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Cai, Mingzhong. Elements Of Classical Recursion Theory: Degree-Theoretic Properties And Combinatorial Properties. Doctor of Philosophy thesis, Cornell University, 2011. https://hdl.handle.net/1813/30687