test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
Abstract
The structure of the semi lattice of the enumeration degrees has been
investigated from many aspects. One aspect is the bounding and
nonbounding properties of the enumeration degrees. Cooper, Sorbi, Lee
and Yang proved that every $\Delta^0_2$ degree bounds a minimal pair,
but there exists a $\Sigma^0_2$ degree that does not bound a minimal
pair. Copestake on the other hand proved that the degree of every
2-generic set bounds a minimal pair and conjectured that there is a
1-generic set whose degree does not bound a minimal pair. Using the
infinite injury priority method we
construct a $\Sigma^0_2$ 1-generic set, whose enumeration degree does
not bound a minimal pair, generalizing the former result and proving
Copestake's longstanding conjecture.
websites: Arnold Beckmann |
2006-04-28 |