|
Organizers |
New characterizations of K-triviality
by
George Barmpalias
Victoria University of Wellington
We present a number of new characterizations of K-triviality, most of which answer some well known questions in algorithmic randomness.Some of these where obtained jointly with coauthors (depending on the result) including Morphett, Montalban, Downey, Greenberg.
As an example:
- a c.e. degree is K-trivial iff it is bounded by an incomplete random degree.
- a delta2 degree A is K-trivial if the number of oracles which compress (in the sense of prefix-free Kolmogorov complexity) better than A is countable.
- a c.e. degree is K-trivial if every c.e. set A computed by it has the property that in any c.e. splitting of A the two halfs induce the same notion of relative randomness.
More characterizations will be given in terms of cupping with a random, and in terms of exact pairs of ideals.
All these results have something in common, namely a general approach to dealing with a lot of problems in randomness, which emerged from the studyof the LR degrees. It is this approach that I am going to focus on in this talk, and how this can be applied to particular problems related to K-triviality.
Date received: March 11, 2008
Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawo-22.