Title | ||
---|---|---|
Kolmogorov Complexity and Information Theory.With an Interpretation in Terms of Questions and Answers |
Abstract | ||
---|---|---|
We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and wherethey are fundamentally different. We discuss and relate the basicnotions of both theories: Shannon entropy, Kolmogorov complexity, Shannon mutual informationand Kolmogorov (``algorithmic'') mutual information. We explainhow universal coding may be viewed as a middle ground betweenthe two theories. We consider Shannon's rate distortion theory, whichquantifies useful (in a certain sense) information.We use the communication of information as our guiding motif, and we explain howit relates to sequential question-answer sessions. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1023/A:1025011119492 | Journal of Logic, Language and Information |
Keywords | DocType | Volume |
kolmogorov complexity,middle ground betweenthe,information theory,elementary theory,mutual information,certain sense,guiding motif,shannon entropy,common purpose,shannon mutual informationand,shannon information,rate distortion theory,data compression,shannon information theory,algorithmic information theory | Journal | 12 |
Issue | ISSN | Citations |
4 | 1572-9583 | 11 |
PageRank | References | Authors |
2.08 | 8 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Grunwald | 1 | 113 | 11.40 |
Paul M. B. Vitá/nyi | 2 | 38 | 4.33 |