A Note on Kolmogorov Complexity and Shannon Entropy
I wrote this report for CS3236 Introduction to Information Theory in AY2022/23 Semester 2. Its motivating question is simple: how should we measure the information contained in a finite binary string when the same object may admit many different encodings? Kolmogorov complexity answers this question through the length of the shortest program that generates the string on a fixed universal computer. The invariance theorem then shows that changing the universal computer alters this quantity by at most an additive constant.
The project led me from Shannon entropy to Turing machines and algorithmic information theory. The most interesting part was understanding how a description-based notion of complexity relates to the distribution-based notion used in Shannon’s theory. This experience later motivated me to take CS3231 Theory of Computation.
One technical subtlety is the distinction between plain and self-delimiting Kolmogorov complexity. Some references leave the convention implicit, although several identities change by logarithmic terms when one moves between the two settings. Reconciling those statements was the most time-consuming part of the project. It also taught me that a rigorous report still needs a deliberate narrative: excessive footnotes may preserve every qualification while obscuring the main argument.
I later encountered Kolmogorov complexity in a rather different context: the KeOps paper interprets symbolic arrays as objects with low descriptive complexity and exploits that structure to reduce memory use. This became practically relevant in my later work with Gaussian processes, where kernel matrix-vector products over large datasets would otherwise exceed GPU memory.