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.