Technical Report 2000-034

Algorithmic Information Theory and Kolmogorov Complexity

Alexander Shen

December 2000

Abstract:

This document contains lecture notes of an introductory course on Kolmogorov complexity. They cover basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), notion of randomness (Martin-Lof randomness, Mises-Church randomness), Solomonoff universal a priori probability and their properties (symmetry of information, connection between a priori probability and prefix complexity, criterion of randomness in terms of complexity) and applications (incompressibility method in computational complexity theory, incompleteness theorems).

Available as compressed Postscript (84 kB, no cover)

Download BibTeX entry.