Shannon Information and Kolmogorov Complexity

Abstract

We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and where they are fundamentally different. We discuss and relate the basic notions of both theories: Shannon entropy versus Kolmogorov complexity, the relation of both to universal coding, Shannon mutual information versus Kolmogorov (`algorithmic') mutual information, probabilistic sufficient statistic versus algorithmic sufficient statistic (related to lossy compression in the Shannon theory versus meaningful information in the Kolmogorov theory), and rate distortion theory versus Kolmogorov's structure function. Part of the material has appeared in print before, scattered through various publications, but this is the first comprehensive systematic comparison. The last mentioned relations are new.

Survey, LaTeX 54 pages, 3 figures, Submitted to IEEE Trans Information Theory

References in corpus (1)

• Forbidden Information

Cited by in corpus (16)

• Identifying Cover Songs Using Information-Theoretic Measures of Similarity
• The free energy requirements of biological organisms; implications for evolution
• A Survey of FPGA Optimization Methods for Data Center Energy Efficiency
• Complexity of Power Draws for Load Disaggregation
• A Note on A Priori Forecasting and Simplicity Bias in Time Series
• An Information-Theoretic Formalism for Multiscale Structure in Complex Systems
• Intelligence, physics and information -- the tradeoff between accuracy and simplicity in machine learning
• Abstraction Mechanisms Predict Generalization in Deep Neural Networks
• MIC: Mutual Information based hierarchical Clustering
• An Algorithmic Approach to Information and Meaning
• An Enrichment Method for Obtaining Biologically Significant Genes from Statistically Significant Differentially Expressed Genes in Comparative Transcriptomics
• Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity
• Algorithmic Problem Complexity
• Subjective Information Measure and Rate Fidelity Theory
• Combinatorial Decision Dags: A Natural Computational Model for General Intelligence
• Indeterministic finite-precision physics and intuitionistic mathematics