Randomness and reducibility

DOI10.1016/J.JCSS.2003.07.004zbMATH Open1072.03024OpenAlexW2019259942MaRDI QIDQ1878680FDOQ1878680

Authors: Denis R. Hirschfeldt, Geoff LaForte, 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

Recommendations

• scientific article; zbMATH DE number 1834658
• Randomness, computability, and density
• Publication:2762505
• Randomness and Solovay degrees
• Reducibilities relating to Schnorr randomness

zbMATH Keywords

dominationSolovay reducibility

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic randomness and complexity.
• A formal theory of inductive inference. Part I
• Weakly computable real numbers
• Process complexity and effective random tests
• A Theory of Program Size Formally Identical to Information Theory
• 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 II
• Constructive dimension equals Kolmogorov complexity
• Incompleteness theorems for random reals
• Randomness, computability, and density
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Three approaches to the quantitative definition of information^*
• Title not available (Why is that?)
• Von Mises' definition of random sequences reconsidered
• Title not available (Why is that?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Title not available (Why is that?)
• Reals which compute little
• Randomness and recursive enumerability
• Title not available (Why is that?)
• Recursive Real Numbers
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Algorithmic Information Theory
• On the definitions of some complexity classes of real numbers
• Title not available (Why is that?)
• Computability Theory and Differential Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• There is no SW-complete c.e. real
• Recursion Theory and Dedekind Cuts
• Cohesive sets and recursively enumerable Dedekind cuts
• A characterization of c. e. random reals
• On the continued fraction representation of computable real numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursive real numbers
• Relatively recursive reals and real functions
• The fractal nature of Riem/Diff. I.
• Presentations of computably enumerable reals.
• Title not available (Why is that?)
• Kolmogorov complexity
• Trivial Reals
• Title not available (Why is that?)

Cited In (42)

• Universal computably enumerable sets and initial segment prefix-free complexity
• Oscillation in the initial segment complexity of random reals
• Universal recursively enumerable sets of strings
• The ibT degrees of computably enumerable sets are not dense
• Some Questions in Computable Mathematics
• Factoring Solovay-random extensions, with application to the reduction property
• Reducibilities relating to Schnorr randomness
• Randomness and recursive enumerability
• Computability Results Used in Differential Geometry
• Compressibility and Kolmogorov complexity
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• Initial segment complexities of randomness notions
• Bounded Turing reductions and data processing inequalities for sequences
• Oreals with \(\Delta_2^0\)-bounded complexity and compressive power
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• Structures of some strong reducibilities
• Genericity of weakly computable objects
• Solovay reducibility and continuity
• Calibrating Randomness
• Randomness and Computability: Open Questions
• Title not available (Why is that?)
• Coherence of reducibilities with randomness notions
• Degrees of randomized computability
• Strong reductions in effective randomness
• Mass Problems and Randomness
• Reducing Randomness via Irrational Numbers
• A minimal pair of 𝐾-degrees
• The computable Lipschitz degrees of computably enumerable sets are not dense
• Universal Recursively Enumerable Sets of Strings
• Random Oracle Reducibility
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Relative randomness and real closed fields
• 2004 Annual Meeting of the Association for Symbolic Logic
• Randomness, computability, and density
• Randomness and the linear degrees of computability
• Algorithmic randomness and measures of complexity
• Where join preservation fails in the bounded Turing degrees of c.e. sets
• Computing and Combinatorics
• Computing and Combinatorics
• On initial segment complexity and degrees of randomness
• Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees
• On the strongly bounded Turing degrees of the computably enumerable sets

This page was built for publication: Randomness and reducibility

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