Several results in program size complexity

DOI10.1016/0304-3975(81)90083-9MaRDI QIDQ1152214zbMATH OpenOpenAlexFDO

Authors Howard P. Katseff, Michael Sipser

Publication date 1981

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(81)90083-9

zbMATH Keywords

binary stringKolmogorov's complexity measure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity
• Complexity dips in random infinite binary sequences
• Information-theoretic characterizations of recursive infinite strings
• Noncomplex sequences: characterizations and examples
• On Kolmogorov's complexity and information
• On degrees of unsolvability
• On non-computable functions
• On the size of machines
• Program size, oracles, and the jump operation

Cited in

(1)

• Kolmogorov complexity for possibly infinite computations

This page was built for publication: Several results in program size complexity

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