Algorithmic information theory

DOI10.2307/2274821zbMath0713.03001OpenAlexW2059835508MaRDI QIDQ3197800

Michiel Marian Michiel van Lambalgen

Publication date: 1989

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://dare.uva.nl/personal/pure/en/publications/algorithmic-information-theory(3d79c1da-640d-478d-b057-17f56bc2892b).html

zbMATH Keywords

thermodynamicsKolmogorov complexityGödel's first incompleteness theoremchaos theoryrandomnessinformation contentr.e. setsChaitin's incompleteness theorem

Mathematics Subject Classification ID

Philosophy of mathematics (00A30) Philosophical and critical aspects of logic and foundations (03A05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Information theory (general) (94A15) Recursively (computably) enumerable sets and degrees (03D25) Proof theory in general (including proof-theoretic semantics) (03F03)

Related Items

Observation of Unbounded Novelty in Evolutionary Algorithms is Unknowable, Is complexity a source of incompleteness?, On constructivity and the Rosser property: a closer look at some Gödelean proofs, INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH, On Characteristic Constants of Theories Defined by Kolmogorov Complexity, Models and the dynamics of theory-building in physics. I: Modeling strategies, Revisiting Chaitin's incompleteness theorem, The scope of Gödel's first incompleteness theorem, On explicating the concept `the power of an arithmetical theory', Kolmogorov complexity and characteristic constants of formal theories of arithmetic, On interpreting Chaitin's incompleteness theorem, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness