Computably enumerable sets below random sets

DOI10.1016/j.apal.2011.12.011zbMath1314.03040OpenAlexW2068521092MaRDI QIDQ450954

André Nies

Publication date: 26 September 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.12.011

zbMATH Keywords

lownesscomputabilityDemuth randomness

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Related Items (5)

Demuth’s Path to Randomness ⋮ STRONG JUMP-TRACEABILITY ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Inherent enumerability of strong jump-traceability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong jump-traceability. II: \(K\)-triviality
• Characterizing the strongly jump-traceable sets via randomness
• Demuth randomness and computational complexity
• Information-theoretic characterizations of recursive infinite strings
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and approximations of the jump
• Lowness properties and randomness
• A random set which only computes strongly jump-traceable c.e. sets
• Benign cost functions and lowness properties
• Lowness for Demuth Randomness
• Relativizations of randomness and genericity notions
• Using random sets as oracles
• Computability and Randomness

This page was built for publication: Computably enumerable sets below random sets