Blog Archives

Topic Archive: Kolmogorov complexity

NERDS: New England Recursion & Definability SeminarSunday, November 6, 20161:40 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

Andre Nies

Structure within the class of K-trivial sets

University of Auckland

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. Since 2002, many alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked amorphous. More recently, internal structure has been found. Bienvenu et al (JEMS, 2016) showed that there is a “smart” K-trivial set, in the sense that any ML-random computing it must compute all K-trivials. Greenberg, Miller and Nies (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches via cost functions.

Chris Conidis
College of Staten Island - CUNY
Prof. Conidis received his Ph.D. in mathematics from the University of Chicago in 2009, under the supervision of Denis Hirschfeldt, Antonio Montalban, and Robert Soare, and subsequently held postdoctoral positions at the University of Waterloo and at Vanderbilt University. His work applies techniques of computability theory to problems in algebra, analysis, and combinatorics. He is now an Assistant Professor at the College of Staten Island in CUNY.