Algorithmic information theory

1989/12/01 by Michiel van Lambalgen · 7 citations
Computer Science · #Computability, Logic, AI Algorithms #semigroups and automata theory #Machine Learning and Algorithms #Computer science

paper · doi:10.1017/s0022481200041153

published in Journal of Symbolic Logic 54(4), 1389-1400 (Cambridge University Press)

openalex publication_date 1989/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21

Abstract

Abstract We present a critical discussion of the claim (most forcefully propounded by Chaitin) that algorithmic information theory sheds new light on Gödel's first incompleteness theorem.

Citations

• Logical basis for information theory and probability theory
• A Theory of Program Size Formally Identical to Information Theory
• The definition of random sequences
• Information-Theoretic Limitations of Formal Systems
• Algorithmic Information Theory

Cited by

• Algorithmic information theory [wikipedia]