COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS

DOI10.1017/jsl.2015.70zbMath1403.03069arXiv1505.01707OpenAlexW2963133035MaRDI QIDQ2976378

Rutger Kuyper, Paul E. Schupp, Denis R. Hirschfeldt, Carl G. jun. Jockusch

Publication date: 28 April 2017

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

Full work available at URL: https://arxiv.org/abs/1505.01707

zbMATH Keywords

algorithmic randomness\(K\)-trivialitycoarse reducibility

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items (8)

THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ A MINIMAL PAIR IN THE GENERIC DEGREES ⋮ DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES ⋮ Computing from projections of random points ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Lowness, Randomness, and Computable Analysis ⋮ Some Questions in Computable Mathematics ⋮ Asymptotic density and computability

Cites Work

• Characterizing the strongly jump-traceable sets via randomness
• Lowness for genericity
• Splitting properties and jump classes
• Generic-case complexity, decision problems in group theory, and random walks.
• Generic computability, Turing degrees, and asymptotic density
• COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS
• Algorithmic Randomness and Complexity
• Asymptotic density, immunity and randomness
• A fixed-point-free minimal degree
• Using random sets as oracles
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• An inequality related to the isoperimetric inequality

This page was built for publication: COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS