On the existence of a strong minimal pair
We show that there is a strong minimal pair in the computably enumerable Turing degrees.
Source author record
Mingzhong Cai
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
3works
2topics
4close collaborators
Published work
3 publications
preprint2015arXiv
DNR and incomparable Turing degrees
We construct an increasing ω-sequence (an) of Turing degrees which forms an initial segment of the Turing degrees, and such that each~an+1 is diagonally noncomputable relative to an. It follows that the~DNR principle of reverse mathematics does not imply the existence of Turing incomparable degrees.
Open access
preprint2014arXiv
Random strings and tt-degrees of Turing complete C.E. sets
We investigate the truth-table degrees of (co-)c.e.\ sets, in particular, sets of random strings. It is known that the set of random strings with respect to any universal prefix-free machine is Turing complete, but that truth-table completeness depends on the choice of universal machine. We show that for such sets of random strings, any finite set of their truth-table degrees do not meet to the degree~0, even within the c.e. truth-table degrees, but when taking the meet over all such truth-table degrees, the infinite meet is indeed~0. The latter result proves a conjecture of Allender, Friedman and Gasarch. We also show that there are two Turing complete c.e. sets whose truth-table degrees form a minimal pair.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.