A rigorous journey through algorithmic information theory, from the shortest description of a string to the deepest notion of randomness. Rebuilt chapter by chapter as interactive lessons.
Optimal descriptions, Kolmogorov complexity, Berry's paradox, and first applications.
Definition, counting argument, incompressible strings, and algorithmic properties.
Encoding pairs, conditional descriptions, the Kolmogorov-Levin theorem.
Measures, the Strong Law, effectively null sets, and randomness deficiencies.
Semimeasures, prefix machines, the main theorem on prefix complexity.
Levin-Schnorr theorem, the random number Ω, Hausdorff dimension.
Decision complexity, comparing complexities, conditional variants, oracles.
Shannon entropy, conditional entropy, the bridge between information theory and complexity.
Infinitely many primes, tape complexity, finite automata, forbidden substrings.