The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

SAS

Seminar

Exact pairs for the ideal of the $K$-trivial sequences in the Turing degrees

Barmpalias, G (Chinese Academy of Sciences)
Thursday 05 July 2012, 11:00-12:00

Seminar Room 1, Newton Institute

Abstract

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.

Presentation

[pdf ]

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧