SHOW / EPISODE

Kolmogorov Complexity and Algorithmic Randomness

Season 1 | Episode 25
21m | Nov 4, 2024

This episode breaks down the 'Kolmogorov Complexity' paper, which discusses the fascinating topic of algorithmic information theory, which explores the inherent complexity of representing information using algorithms. It defines Kolmogorov complexity, a measure of the shortest computer program needed to describe a piece of data. The text then examines various related concepts like conditional complexityprefix complexity, and monotone complexity, ultimately exploring their connections with algorithmic randomness. It delves into the nature of random sequences, contrasting computable randomness with the more intuitive Mises-Church randomness, and analyses the impact of selection rules on randomness. The chapter also explores relationships between entropycomplexity, and size and offers insights into multisource information theory and algorithmic statistics.


Audio : (Spotify) https://open.spotify.com/episode/1EhNcxqkmGE7uVLhs583DL?si=OgDArRDTQ0mHF-O1j-Jwkg

Paper: https://www.lirmm.fr/~ashen/kolmbook-eng-scan.pdf

Paused
Audio Player Image
Marvin's Memos
Loading...