Kolmogorov complexity

The information content of finite strings measured by the length of their shortest descriptions: the invariance theorem, incompressible strings and the non-computability of complexity, the complexity of initial segments of infinite sequences, prefix-free machines and the complexity K, the KC theorem, the coding theorem, and the halting probability Ω.

Contents

1. 1

   Plain Kolmogorov complexity

   The complexity of a string is the length of its shortest description by an optimal machine; the invariance theorem; incompressible strings; the complexity function is not computable but is approximable from above.

   1. 1.1 Conventions
   2. 1.2 Description machines
   3. 1.3 Incompressible strings
   4. 1.4 Pairs
   5. 1.5 Non-computability
   6. 1.6 Exercises
   7. 1.7 Notes and references
   40 min
2. 2

   Complexity of initial segments

   The complexity of the initial segments of an infinite sequence; computable sequences have minimal complexity; every sequence has prefixes compressible by any constant; the lower envelope of the complexity of numbers.

   1. 2.1 Computable sequences
   2. 2.2 Oscillation
   3. 2.3 The lower envelope of the complexity of numbers
   4. 2.4 Exercises
   5. 2.5 Notes and references
   35 min
3. 3

   Prefix-free complexity

   Machines whose domain is prefix-free; the optimal prefix-free machine and the complexity K; subadditivity, the Kraft inequality, and the comparison between K and C.

   1. 3.1 Prefix-free machines
   2. 3.2 Properties of K
   3. 3.3 Prefix-free complexity of initial segments
   4. 3.4 Exercises
   5. 3.5 Notes and references
   40 min
4. 4

   The KC theorem and the coding theorem

   Building prefix-free machines from bounded request sets; K is the least right-c.e. function satisfying the Kraft inequality; the coding theorem identifies K with the logarithm of the halting probability of a string; counting strings of small complexity; Chaitin's number Ω.

   1. 4.1 Bounded request sets
   2. 4.2 The characterization of K
   3. 4.3 The coding theorem
   4. 4.4 Chaitin's halting probability
   5. 4.5 Exercises
   6. 4.6 Notes and references
   45 min