BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Andre Nies (University of Auckland)
DTSTART:20200826T010000Z
DTEND:20200826T020000Z
DTSTAMP:20260423T005724Z
UID:CTA/19
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CTA/19/">Dis
 covering structure within the class of K-trivial sets</a>\nby Andre Nies (
 University of Auckland) as part of Computability theory and applications\n
 \n\nAbstract\nJoint work with Noam Greenberg\, Joseph Miller\, and Dan Tur
 etsky\n\nThe K-trivial sets are antirandom in the sense that the initial s
 egment complexity in terms of prefix-free Kolmogorov complexity K grows as
  slowly as possible. Chaitin introduced this notion in about 1975\, and sh
 owed that each K-trivial is Turing below the halting set. Shortly after\, 
 Solovay proved   that a K-trivial set can be noncomputable. \n\nIn the pas
 t two decades\, many alternative characterisations of this class have been
  found: properties such as  being low for K\, low for Martin-Löf (ML) ra
 ndomness\, and a basis for  ML randomness\, which state in one way or the
  other that the set is close to computable. \n\nInitially\, the class of 
 noncomputable K-trivials appeared to be  amorphous. More recently\, eviden
 ce of an internal structure has been found. Most of these results can be p
 hrased in the language of a mysterious  reducibility on the K-trivials whi
 ch is weaker than Turing’s: A is ML-below B if each ML-random computing 
 B also computes A.\n\nBienvenu\, Greenberg\, Kucera\, Nies and Turetsky (J
 EMS 2016) showed that there an ML complete K-trivial set. Greenberg\, Mill
 er and Nies  (JML\, 2019) established   a dense hierarchy of subclasses o
 f the K-trivials based on fragments of Omega computing the set\, and each 
 such subclass is an initial segment for ML.  More recent results  generali
 se these approaches using cost functions. They also show that each K-trivi
 al set  is ML-equivalent to a c.e. K-trivial. \n\nThe 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 ope
 n questions. For instance\, is ML-completeness an arithmetical property of
  K-trivials?\n
LOCATION:https://researchseminars.org/talk/CTA/19/
END:VEVENT
END:VCALENDAR