marginaliaA PODCASTExplore all episodes

AI & Computer Science

An Introduction to Kolmogorov Complexity and Its Applications (Ming Li and Paul Vitányi)

LISTEN TO THIS EPISODE

Source cover or paper first page: An Introduction to Kolmogorov Complexity and Its Applications

Ming Li and Paul Vitányi study the information in an individual object through the length of a shortest computer program that produces it.

The discussion follows the fourth edition from plain and prefix complexity to randomness, algorithmic probability, and induction.

Incompressibility supplies a method for proving results even though exact Kolmogorov complexity has no general computing algorithm.

Resource bounds and logical depth distinguish a short description from the work required to produce its output.

Applications connect these ideas with learning, information distance, practical compression, and the physics of computation.

Listen on the podcast website

Read about the original source: An Introduction to Kolmogorov Complexity and Its Applications

Part of Marginalia: books, papers, and ideas for learning and debate.