University of Cambridge > > Isaac Newton Institute Seminar Series > 20 years of K-triviality

20 years of K-triviality

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact nobody.

SASW09 - International conference on computability, complexity and randomness

In June 2012, I gave a talk at Chicheley Hall entitled “10 Years of Triviality”, in connection with the Turing year. The current talk will trace the developments in the area of K-trivial sets of natural numbers that took place since then. Several further characterisation of this class were obtained, taking the total to 18 or so. The covering problem (whether above each K-trivial there is an incomplete ML-random) was solved in the affirmative by a collaboration of seven researchers in the same year 2012. Later on, researchers addressed the internal structure of the class of K-trivial sets, using a reducibility coarser than Turing’s: A is ML-below B if every ML-random computing B also computes A. It turns out that the K-trivial sets are well behaved under ML-reducibility; in particular, there is a complete K-trivial, and there are no minimal pairs. Sadly, we don’t know to this day whether ML-reducibility is arithmetical.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity