For my research project I use a measure that approximates Kolmogorov complexity of some time-series. But actually, it was quite interesting to trace the whole link to the basic theory and see why I cannot simply compute Kolmogorov complexity as it stands. Without a hint of doubt the answer to such question can be easily found. But still some explanation looks a bit dumb whereas others contain too much formalism for me to grasp. So I have got this widely recommended book by Thomas Cover and found really clear arguments there. In the next few paragraphs I would like to project the perceived knowledge.

Let's start with Gödel's incompleteness theorem that says that any interesting system in mathematics is not complete. There are statements that looks like true, but cannot actually be proved within that only system (due to self referencing). E.g. Epimenides liar paradox

• Next statement is false
• Previous statement is true

Then, a halting problem appeared from the incompleteness theorem. It states that for any generic program it is impossible to define weather the program finally stops or not. For any. Not a particular predefined one.

Finally, computation of Kolmogorov Complexity comes from a halting problem. In order to find the shortest program to output the sequence one needs to go through all the shorter programs and see if that program can fully describe the input. In such terms, the shortest program needs to halt at some point. But a general program may not necessarily stop, therefore Kolmogorov complexity is non computable.

P.S. to keep things simple, links are likely to go to wiki.

If you enjoyed this post, make sure you subscribe to my RSS feed!