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

Authors
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.
Keywords algorithmic information theory  data compression  Kolmogorov complexity  mutual information  prefix codes  rate distortion theory  Shannon information theory  universal codes
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1025011119492
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 33,741
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

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.

Analytics

Added to PP index
2009-01-28

Total downloads
56 ( #109,439 of 2,263,083 )

Recent downloads (6 months)
7 ( #53,219 of 2,263,083 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature