COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Exact pairs for the ideal of the $K$-trivial sequences in the Turing degrees

## Exact pairs for the ideal of the $K$-trivial sequences in the Turing degreesAdd to your list(s) Download to your calendar using vCal - Barmpalias, G (Chinese Academy of Sciences)
- Thursday 05 July 2012, 11:00-12:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing The $K$-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable (c.e.) members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in a published list of questions in the Bulletin of Symbolic Logic in 2006 by Miller and Nies and later in Nies’ book on computability and randomness. Moreover it was featured in several conferences in algorithmic randomness, since 2005. We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists a $K$-trivial degree $mathbf{d}$ such that for all degrees $mathbf{a}, mathbf{b}$ which are not $K$-trivial and $mathbf{a}>mathbf{d}, mathbf{b}>mathbf{d}$ there exists a degree $mathbf{v}$ which is not $K$-trivial and $mathbf{a}>mathbf{v}, mathbf{b}>mathbf{v}$. This work sheds light to the question of the definability of the $K$-trivial degrees in the c.e. degrees. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsCambridge Society for Economic Pluralism Women's Word NUDT Visitors Seminars## Other talksCohomology of the moduli space of curves What we don’t know about the Universe from the very small to the very big : ONE DAY MEETING Smooth muscle specific alternative splicing: super-enhancers point the way A cabinet of natural history: the long-lost Paston collection Borel Local Lemma Modelling mitochondrial dysfunction in Parkinson’s disease: mitophagy, calcium and beyond |