Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers

Journal of Logic, Language and Information 12 (4):497-529 (2003)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 77,869

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Intrinsic information.John D. Collier - 1990 - In Philip P. Hanson (ed.), Information, Language and Cognition. University of British Columbia Press. pp. 1--390.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Quantum information does not exist.Armond Duwell - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (3):479-499.
The transmission sense of information.Carl T. Bergstrom & Martin Rosvall - 2011 - Biology and Philosophy 26 (2):159-176.
Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.


Added to PP

98 (#131,419)

6 months
2 (#325,240)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

A Scientific Metaphysical Naturalisation of Information.Bruce Long - 2018 - Dissertation, University of Sydney
Biological Information as Choice and Construction.Arnaud Pocheville - 2018 - Philosophy of Science 85 (5):1012-1025.
Strengthening Weak Emergence.Nora Berenstain - 2020 - Erkenntnis 87 (5):2457-2474.
Bohmian Mechanics is Not Deterministic.Klaas Landsman - 2022 - Foundations of Physics 52 (4):1-17.

View all 6 citations / Add more citations

References found in this work

A Mathematical Theory of Communication.Claude E. Shannon - 1948 - Bell System Technical Journal 27:379–423.
Quality and quantity of information exchange.Robert van Rooy - 2003 - Journal of Logic, Language and Information 12 (4):423-451.
Quality and Quantity of Information Exchange.Robert van Rooy - 2003 - Journal of Logic, Language and Information 12 (4):423-451.
On the Mathematical Foundations of Theoretical Statistics.Ronald A. Fisher - 1922 - Philosophical Transactions of the Royal Society of London. Series A:309--368.

Add more references