An Introduction To Kolmogorov Complexity And Its Applications

Briefly we review the basic elements of computability theory and prob ability theory that are required. Finally in order to place the subject in the appropriate historical and conceptual context we trace the main roots of Kolmogorov complexity. This way the stage is set for Chapters 2 and 3 where we introduce the notion of optimal effective descriptions of objects.