Randomness, relativization and Turing degrees
From MaRDI portal
Publication:5718673
DOI10.2178/jsl/1120224726zbMath1090.03013OpenAlexW2058444173MaRDI QIDQ5718673
André Nies, Sebastiaan A. Terwijn, Frank Stephan
Publication date: 16 January 2006
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.58.4984
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other Turing degree structures (03D28)
Related Items
Demuth’s Path to Randomness ⋮ Reducibilities relating to Schnorr randomness ⋮ Relating and contrasting plain and prefix Kolmogorov complexity ⋮ On the uniform computational content of the Baire category theorem ⋮ Randomness, Computation and Mathematics ⋮ Initial segment complexities of randomness notions ⋮ Low for random reals and positive-measure domination ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ Randomness and universal machines ⋮ LUZIN’S (N) AND RANDOMNESS REFLECTION ⋮ Genericity and UD-random reals ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ Depth, Highness and DNR Degrees ⋮ DEEP CLASSES ⋮ Continuous randomness via transformations of 2-random sequences ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ On initial segment complexity and degrees of randomness ⋮ Effectively approximating measurable sets by open sets ⋮ Growth and irreducibility in path-incompressible trees ⋮ Strength and Weakness in Computable Structure Theory ⋮ Effective Bi-immunity and Randomness ⋮ Demuth randomness and computational complexity ⋮ Limit complexities revisited ⋮ Schnorr trivial reals: a construction ⋮ Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ The Information Content of Typical Reals ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Lowness of higher randomness notions ⋮ Canonical immunity and genericity ⋮ Schnorr trivial sets and truth-table reducibility ⋮ Strong reductions in effective randomness ⋮ Schnorr Trivial Reals: A construction ⋮ Effective Randomness for Computable Probability Measures ⋮ On low for speed oracles ⋮ Relativized Schnorr tests with universal behavior ⋮ Coherence of reducibilities with randomness notions ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Hyperimmune-free degrees and Schnorr triviality ⋮ RELATIVIZING CHAITIN'S HALTING PROBABILITY ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Difference randomness ⋮ Lowness for Kurtz randomness ⋮ Highness properties close to PA completeness ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ On a conjecture of Dobrinen and Simpson concerning almost everywhere domination ⋮ Randomness and initial segment complexity for measures ⋮ Constructive equivalence relations on computable probability measures ⋮ Randomness and Computability: Open Questions ⋮ Calibrating Randomness ⋮ When van Lambalgen’s Theorem fails ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ Unified characterizations of lowness properties via Kolmogorov complexity ⋮ On partial randomness ⋮ Integer valued betting strategies and Turing degrees ⋮ Trivial measures are not so trivial ⋮ KL-randomness and effective dimension under strong reducibility
Cites Work
- Unnamed Item
- On relative randomness
- Computational randomness and lowness
- Randomness and Recursive Enumerability
- Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
- A Theory of Program Size Formally Identical to Information Theory
- Lowness for the class of random sets
- Complexity oscillations in infinite binary sequences
- A unified approach to the definition of random sequences
- The definition of random sequences
