In 2023, Alice and Bob play a game of coin tosses to determine the most number of tails. Bob’s all-tails sequence raises suspicion from Alice, who questions the randomness of the outcomes. Bob uses probability to defend himself, but Alice argues that probability does not accurately reflect randomness. The post introduces Kolmogorov Complexity as a mathematical tool to describe the randomness of a string. Kolmogorov complexity is further explored to address the issue of language dependency, leading to the concept of a universal language. The post also discusses Normalized Information Distance and Normalized Compression Distance to compare the similarity between strings. In the end, Alice outsmarts Bob using her new knowledge.
https://smunshi.net/kolmogorov-complexity-and-compression-distance.html