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)
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)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Effective Complexity as a Measure of Information Content.James W. McAllister - 2003 - Philosophy of Science 70 (2):302-307.
The Stories of Logic and Information.Johan van Benthem, Maricarmen Martinez, David Israel & John Perry - unknown
Algorithmic Information Theory and Undecidability.Panu Raatikainen - 2000 - Synthese 123 (2):217-225.
Intrinsic Information.John D. Collier - 1990 - In Philip P. Hanson (ed.), Information, Language and Cognition. University of British Columbia Press. pp. 1--390.
Chaos and Randomness: An Equivalence Proof of a Generalized Version of the Shannon Entropy and the Kolmogorov–Sinai Entropy for Hamiltonian Dynamical Systems.Roman Frigg - manuscript
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
In What Sense is the Kolmogorov-Sinai Entropy a Measure for Chaotic Behaviour?—Bridging the Gap Between Dynamical Systems Theory and Communication Theory.Roman Frigg - 2004 - British Journal for the Philosophy of Science 55 (3):411 - 434.
Quantum Information Does Not Exist.A. Duwell - 2003 - Studies in History and Philosophy of Science Part B 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 index2009-01-28
Total downloads41 ( #123,281 of 2,153,485 )
Recent downloads (6 months)2 ( #280,610 of 2,153,485 )
How can I increase my downloads?