20 years of K-triviality

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

• Andre Nies (University of Auckland)
• Tuesday 07 June 2022, 13:30-14:30
• Seminar Room 1, Newton Institute.

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.

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.