Randomness and reducibility
From MaRDI portal
Publication:1878680
DOI10.1016/j.jcss.2003.07.004zbMath1072.03024OpenAlexW2019259942MaRDI QIDQ1878680
Geoff LaForte, Denis R. Hirschfeldt, Rodney G. Downey
Publication date: 8 September 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.004
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Genericity of weakly computable objects, Initial segment complexities of randomness notions, Randomness and the linear degrees of computability, Where join preservation fails in the bounded Turing degrees of c.e. sets, Universal computably enumerable sets and initial segment prefix-free complexity, Compressibility and Kolmogorov complexity, On initial segment complexity and degrees of randomness, Maximal pairs of computably enumerable sets in the computably Lipschitz degrees, Oscillation in the initial segment complexity of random reals, The computable Lipschitz degrees of computably enumerable sets are not dense, On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets, Some Questions in Computable Mathematics, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER, Universal Recursively Enumerable Sets of Strings, Structures of Some Strong Reducibilities, Universal recursively enumerable sets of strings, Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees, The ibT degrees of computably enumerable sets are not dense, Bounded Turing reductions and data processing inequalities for sequences, A uniform version of non-\(\mathrm{low}_{2}\)-ness, 2004 Annual Meeting of the Association for Symbolic Logic, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Relative randomness and real closed fields, A minimal pair of 𝐾-degrees, Randomness and Computability: Open Questions, Calibrating Randomness, Computability Results Used in Differential Geometry
Cites Work
- Constructive dimension equals Kolmogorov complexity
- On the continued fraction representation of computable real numbers
- Incompleteness theorems for random reals
- Relatively recursive reals and real functions
- The fractal nature of Riem/Diff. I.
- Presentations of computably enumerable reals.
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- Process complexity and effective random tests
- Cohesive sets and recursively enumerable Dedekind cuts
- Randomness and Recursive Enumerability
- Randomness, Computability, and Density
- Algorithmic Randomness and Complexity
- On the definitions of some complexity classes of real numbers
- Von Mises' definition of random sequences reconsidered
- A Theory of Program Size Formally Identical to Information Theory
- Algorithmic Information Theory
- Trivial Reals
- There is no SW-complete c.e. real
- Three approaches to the quantitative definition of information*
- Recursion Theory and Dedekind Cuts
- Recursive real numbers
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The definition of random sequences
- A formal theory of inductive inference. Part I
- A formal theory of inductive inference. Part II
- Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
- Computability Theory and Differential Geometry
- Recursive Real Numbers
- Weakly computable real numbers
- A characterization of c. e. random reals
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
