Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers
Graduate studies at Western
Journal of Logic, Language and Information 12 (4):497-529 (2003)
|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)|
|Through your library||Configure|
Similar books and articles
James W. McAllister (2003). Effective Complexity as a Measure of Information Content. Philosophy of Science 70 (2):302-307.
Johan van Benthem, Maricarmen Martinez, David Israel & John Perry, The Stories of Logic and Information.
Panu Raatikainen (2000). Algorithmic Information Theory and Undecidability. Synthese 123 (2):217-225.
Roman Frigg, Chaos and Randomness: An Equivalence Proof of a Generalized Version of the Shannon Entropy and the Kolmogorov–Sinai Entropy for Hamiltonian Dynamical Systems.
Joseph S. Miller (2004). Every 2-Random Real is Kolmogorov Random. Journal of Symbolic Logic 69 (3):907-913.
Roman Frigg (2004). In What Sense is the Kolmogorov-Sinai Entropy a Measure for Chaotic Behaviour?—Bridging the Gap Between Dynamical Systems Theory and Communication Theory. British Journal for the Philosophy of Science 55 (3):411 - 434.
A. Duwell (2003). Quantum Information Does Not Exist. Studies in History and Philosophy of Science Part B 34 (3):479-499.
Carl T. Bergstrom & Martin Rosvall (2011). The Transmission Sense of Information. Biology and Philosophy 26 (2):159-176.
Verónica Becher & Santiago Figueira (2005). Kolmogorov Complexity for Possibly Infinite Computations. Journal of Logic, Language and Information 14 (2):133-148.
Added to index2009-01-28
Total downloads10 ( #114,432 of 739,350 )
Recent downloads (6 months)2 ( #37,186 of 739,350 )
How can I increase my downloads?