Thursday, 18 October 2012, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: Probability theory is very good at describing randomness of collections. However, the intuitive concept of randomness also includes lack of evident order in objects, and this is not well addressed by only probabilistic means. Algorithmic information theory deals with the problem of defining and studying randomness of single objects.
In this talk, which will be an introductory overview, we will consider the basics of algorithmic information theory, such as Kolmogorov complexity and Martin-Löf tests, which allow to talk about randomness of single strings. We will also consider a formulation by Hertling and Weihrauch, which allows to define randomness of more general objects such as d-dimensional configurations.