4
$\begingroup$

In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth).

As far as I understand, algorithmic information theory was developed separately from information theory, and Kolmogorov didnt formalize AIT in terms of shannon entropy and so forth (am I wrong?)

How connected are the two fields? Are they really about quite separate things? Are there only some marginal connections? Or are they deeply connected?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I don't have the background to give a deep answer about how deeply connected the fields are, but Li and Vitanyi's An Introduction to Kolmogorov Complexity and Its Applications--probably the most widely known textbook on AIT--repeatedly incorporates mathematical and conceptual material from information theory (such as Shannon entropy) into its presentation of AIT. Here is a quotation from the third edition (p. 73) that illustrates a connection that might be considered deep:

We are interested in a measure of information content of an individual finite object, and in the information conveyed about an individual finite object by another individual finite object. Here, we want the information content of an object x to be an attribute of x alone, and not to depend on, for instance, the means chosen to describe this information content. Making the natural restriction that the description method should be effective, the information content of an object should be recursively invariant (Section 1.7) among the different description systems. Pursuing this thought leads straightforwardly to Kolmogorov complexity.

(Apart from the fact that most of the paragraph clearly seems to be discussing Shannon information, it comes immediately after a paragraph that discusses a quotation by Shannon.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Shannon information only applies to random variables, whereas the paragraph is about fixed objects. $\endgroup$
    – Yuval Filmus
    Dec 16, 2019 at 22:56
  • $\begingroup$ Yes, @YuvalFilmus, good point. The paragraphs that precede this one contain remarks that connect the RVs in information theory to sequences, at least informally. I'm reluctant to quote several paragraphs, but in context Li and Vitanyi are clearly suggesting that there are relevant relationships between Shannon information and Kolmogorov complexity. L&V are viewing a finite sequence as, kind of sort of, generated by a random process. These remarks from an early chapter are informal, but relationships of various sorts between information theory and AIT come up repeatedly in later chapters. $\endgroup$
    – Mars
    Dec 17, 2019 at 10:18
  • $\begingroup$ On the other hand, I think that people writing about AIT sometimes talk about sequences being generated by random processes, but then go on and focus solely on the sequences themselves. Maybe that kind of slight of hand is what's going on in this particular part of this book. $\endgroup$
    – Mars
    Dec 17, 2019 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.