2008 seminar talk: Algorithmic randomness (thick Π01 classes)

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


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 Π01 classes of positive measure will be pointed out (as a kind of thick Π01 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 Π01 classes, will be explained. If time permits, LR-reducibility (LR stands for low for random) will be explained together with its importance.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.