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
Steffen Lempp
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
4works
2topics
4close collaborators
Published work
4 publications
preprint2014arXiv
Comparing DNR and WWKL
In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).
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
preprint2014arXiv
The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
We study the reverse mathematics and computability-the\-o\-re\-tic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that SRT22 implies DNR over RCA0 but COH does not, and answer a question of Mileti by showing that every computable stable 2-coloring of pairs has an incomplete Δ20 infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT22 does not imply RT22.
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.