Kolmogorov-Complexity Based on Infinite Computations

DOI10.1007/978-3-642-03456-5_4MaRDI QIDQ3644713zbMATH OpenOpenAlexFDO

Authors Günter Hotz

Publication date 12 November 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03456-5_4

zbMATH Keywords

collectivesinfinite computationsmonotone Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Kolmogorov complexity and probability measures.
• On minimal-program complexity measures
• Program size complexity for possibly infinite computations
• Chaitin complexity, Shannon information content of a single event and infinite random sequences. I
• scientific article; zbMATH DE number 4102487

Cites work

• Algorithmic Information Theory
• Analytic machines
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 1216200 (Why is no real title available?)
• On the Length of Programs for Computing Finite Binary Sequences
• The definition of random sequences
• Theories of computational complexity
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(14)

• Kolmogorov complexity for possibly infinite computations
• Descriptive complexity of computable sequences revisited
• Kolmogorov complexity of enumerating finite sets
• Asymptotic orbit complexity of infinite measure preserving transformations
• On Kolmogorov complexity in the real Turing machine setting
• On the information carried by programs about the objects they compute
• Estimates of Kolmogorov complexity in approximating Cantor sets
• Kolmogorov complexity and probability measures.
• Strict process machine complexity
• scientific article; zbMATH DE number 1048038 (Why is no real title available?)
• scientific article; zbMATH DE number 3999902 (Why is no real title available?)
• On minimal-program complexity measures
• Program size complexity for possibly infinite computations
• Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets

This page was built for publication: Kolmogorov-Complexity Based on Infinite Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3644713)