Degrees of monotone complexity

DOI10.2178/jsl/1164060458zbMath1109.03033OpenAlexW1964985604MaRDI QIDQ3416117

William C. Calhoun

Publication date: 19 January 2007

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.576.302

zbMATH Keywords

monotone complexitycomputably enumerable realsmonotone degreerelative randomness of reals

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (2)

On the computational power of random strings ⋮ Increasing the gap between descriptional complexity and algorithmic probability

Cites Work

• Unnamed Item
• Program size complexity for possibly infinite computations
• Process complexity and effective random tests
• The recursively enumerable degrees are dense
• Lowness properties and randomness
• Randomness, Computability, and Density
• Algorithmic Randomness and Complexity
• A Theory of Program Size Formally Identical to Information Theory
• Relations between varieties of kolmogorov complexities
• On the Length of Programs for Computing Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• A variant of the Kolmogorov concept of complexity
• A formal theory of inductive inference. Part II
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

This page was built for publication: Degrees of monotone complexity