Ian Herbert: Kolmogorov Complexity, Lowness Notions, and Finite Self-Information

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 04 September 2013, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Ian Herbert

Title: Kolmogorov Complexity, Lowness Notions, and Finite Self-Information

The (prefix-free) Kolmogorov complexity of a finite binary string is the
length of the shortest description of the string, and can be thought of as
a measure of that string’s information content. This notion can be extended
to deal with reals (i.e. infinite binary strings) either by taking the
Kolmogorov complexity of finite initial segments of the real or by
examining the effect on the Kolmogorov complexities of strings when using
the real as an oracle. Each of these notions has an associated notion of
the `minimal possible’ amount of information of a real. We examine a
definition of mutual information for reals due to Levin which induces its
own lowness notion: having finite self-information, which is a real’s
mutual information with itself. The talk will examine the interactions
between these lowness notions and related concepts.


Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.