Discovering structure within the class of K-trivial sets

Abstract: Joint work with Noam Greenberg, Joseph Miller, and Dan Turetsky

The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Chaitin introduced this notion in about 1975, and showed that each K-trivial is Turing below the halting set. Shortly after, Solovay proved that a K-trivial set can be noncomputable.

In the past two decades, many alternative characterisations of this class have been found: properties such as  being low for K, low for Martin-Löf (ML) randomness, and a basis for  ML randomness, which state in one way or the other that the set is close to computable. 

Initially, the class of noncomputable K-trivials appeared to be amorphous. More recently, evidence of an internal structure has been found. Most of these results can be phrased in the language of a mysterious reducibility on the K-trivials which is weaker than Turing’s: A is ML-below B if each ML-random computing B also computes A.

Bienvenu, Greenberg, Kucera, Nies and Turetsky (JEMS 2016) showed that there an ML complete K-trivial set. Greenberg, Miller and Nies  (JML, 2019) established a dense hierarchy of subclasses of the K-trivials based on fragments of Omega computing the set, and each such subclass is an initial segment for ML. More recent results generalise these approaches using cost functions. They also show that each K-trivial set is ML-equivalent to a c.e. K-trivial.

The extreme lowness of K-trivials, far from being an obstacle, allows for methods which don’t work in a wider setting. The talk provides an overview and discusses open questions. For instance, is ML-completeness an arithmetical property of K-trivials?

logic

Audience: researchers in the topic

---

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.

---