Algorithmic randomness (thick \Pi^0_1 classes)

20.11.2008 15:00 - 16:30

A. Kučera (Charles U, Prague, CZ)

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

Organiser:

KGRC

Location:
SR 101, 2. St., Währinger Str. 25