The extent and density of sequences within the minimal-program complexity hierarchies

DOI10.1016/S0022-0000(74)80004-8zbMath0293.68044MaRDI QIDQ1212360

Robert P. Daley

Publication date: 1974

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

The Kolmogorov complexity of infinite words ⋮ Exact constructive and computable dimensions ⋮ Research in the theory of inductive inference by GDR mathematicians - A survey ⋮ On Oscillation-free ε-random Sequences ⋮ On the inference of optimal descriptions ⋮ Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension ⋮ On partial randomness ⋮ The Kolmogorov complexity of real numbers.

Cites Work

• Optimal enumerations and optimal gödel numberings
• Minimal-program complexity of sequences with restricted resources
• An Example of Information and Computation Resource Trade-Off
• On minimal-program complexity measures
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item