←

Algorithmic Information Theory

Directed Reading Program, UW-Madison Fall 2026

Algorithmic information theory (sometimes called Kolmogorov complexity theory) is the study of how much “information” lies in a given object (e.g. the constant pi, or a photograph.) It is a broad, interdisciplinary subject, in the locus of theoretical computer science, information theory, statistics, probability theory, and artificial intelligence.

We will have a narrower focus: following Li and Vitányi’s An Introduction to Kolmogorov Complexity Theory and Its Applications, we begin with an introduction to the elementary information theory developed by Shannon in 1948. Afterwards, we will direct our aim to developing the mathematics of algorithmic complexity theory: under differing frameworks, what is the answer to the question “How do we effectively describe objects?”.

We will conclude with some applications of the theory to problems in physics and computation according to student interest; examples include reversible computing, coding theory, thermodynamics, and compression.

Part I: Information Theory

The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point.

(1.0-1.5, 1.11) We develop Shannon’s information theory from combinatorial principles; I would highly recommend reading the original paper, which additionally uses probabilistic assumptions. entropy, prefix codes, the Kraft inequality, optimal codes, and universal codes.

Part II: Complexity

We aim at something different from[…] the information that needs to be transmitted in order to select an object from a previously agreed-upon set of alternatives. Our task is to widen the limited set of alternatives until it is universal. We aim at a notion of absolute information of individual objects, that is, the information that by itself describes the object completely.

2.0-2.2, 2.8, 3.0-3.3, 3.7, 8.1

Part III: Applications

8.3, 8.6, 8.7