Kolmogorov Complexity and Noncomputability

DOI10.1002/1521-3870(200211)48:4%3C574::AID-MALQ574%3E3.0.CO;2-OMaRDI QIDQ4787876zbMATH OpenOpenAlexFDO

Authors George Davie

Publication date 8 January 2003

Full work available at URL https://doi.org/10.1002/1521-3870(200211)48:4%3C574::aid-malq574%3E3.0.co;2-o

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Complexity of proofs (03F20)

Recommendations

• Kolmogorov complexity for possibly infinite computations
• Kolmogorov complexity and the second incompleteness theorem
• scientific article; zbMATH DE number 107775
• Kolmogorov complexity and non-determinism
• scientific article; zbMATH DE number 107774

Cited in

(4)

• scientific article; zbMATH DE number 5294121 (Why is no real title available?)
• On the Kolmogorov-Chaitin Complexity for short sequences
• Logical operations and Kolmogorov complexity
• Kolmogorov complexity and non-determinism

This page was built for publication: Kolmogorov Complexity and Noncomputability

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