Algorithmic Information Theory

1977/07/01 by Gregory J. Chaitin · 1,012 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Algorithms and Data Compression #semigroups and automata theory #Probabilistic logic #Information theory #Formalism (music) #Computer science #Theoretical computer science #Probability theory #Algorithm #Mathematics #Artificial intelligence #Statistics

paper · doi:10.1147/rd.214.0350

published in IBM Journal of Research and Development 21(4), 350-359 (IBM)

openalex publication_date 1977/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02

Abstract

This paper reviews algorithmic information theory, which is an attempt to apply information-theoretic and probabilistic ideas to recursive function theory. Typical concerns in this approach are, for example, the number of bits of information required to specify an algorithm, or the probability that a program whose bits are chosen by coin flipping produces a given output. During the past few years the definitions of algorithmic information theory have been reformulated. The basic features of the new formalism are presented here and certain results of R. M. Solovay are reported.

Citations

• A Model of Set-Theory in Which Every Set of Reals is Lebesgue Measurable
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
• Logical basis for information theory and probability theory
• A Theory of Program Size Formally Identical to Information Theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• Information-Theoretic Limitations of Formal Systems
• A formal theory of inductive inference. Part II

Cited by

• Quantum adiabatic algorithm for Hilbert's tenth problem: I. The algorithm
• Algorithmic information theory
• Grounding Occam's Razor in a Formal Theory of Simplicity
• The definition of a random sequence of qubits: from Noncommutative Algorithmic Probability Theory to Quantum Algorithmic Information Theory and back
• Experimentally probing the algorithmic randomness and incomputability of quantum randomness
• On Approximating Real-World Halting Problems
• Algorithmic information theory [wikipedia]