Kurt Gödel Research Center

2008 seminar talk: Algorithmic randomness (thick Π⁰₁ classes)

Talk held by Antonín Kučera (Charles University, Prague) at the KGRC seminar on 2008-11-20.

Abstract

In the first part of the talk both a survey of various approaches to algorithmic randomness (including Martin-Löf tests, prefix-free Kolmogorov complexity, martingales) and basic facts about properties of 1-random sets will be given. The role of Π⁰₁ classes of positive measure will be pointed out (as a kind of thick Π⁰₁ classes). Generalizations and modifications of the concept of 1-randomness will be mentioned.

The second part of the talk deals with algorithmic weakness, namely with the class of K-trivials and its various other characterizations such as lowness for randomness etc. Among other things an existence of a low T-upper bound for the class of K-trivials will be presented as a corollary of a more general characterization of ideals in T-degrees which have a low T-upper bound (a result of Kucera-Slaman). A substantial role of PA sets (i.e. {0, 1}-valued DNR functions), which form another kind of thick Π⁰₁ classes, will be explained. If time permits, LR-reducibility (LR stands for low for random) will be explained together with its importance.