Prompt enumerations and relative randomness

DOI10.1093/LOGCOM/EXQ049MaRDI QIDQ2907062zbMATH OpenOpenAlexFDO

Authors Anthony Morphett

Publication date 5 September 2012

Published in Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exq049

zbMATH Keywords

c.e. degreesprompt simplicitypromptnessrelative randomness

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Review text

In the paper under review a notion of prompt non-low-for-randomness is introduced. It is analogous to the property of prompt simplicity and to the equivalent property of prompt permitting. The introduced property is a prompt form of non-low-for-random permitting, which is the natural notion of permitting in the context of relative randomness. It is shown that the class of Turing degrees of promptly non-low-for-random c.e. sets is non-trivial and a proper subclass of the non-low-for-random promptly simple degrees. The prompt non-low-for-randomness is also considered in the context of the LR-degrees and LR-reducibility, a weak reducibility arising naturally from relative randomness.

Recommendations

• Randomness, lowness and degrees
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Low upper bounds in the LR degrees
• Incompleteness, approximation and relative randomness
• Randomness, relativization and Turing degrees

Cited in

(3)

• Enumeration, Counting, and Random Generation of Ladder Lotteries
• Working with the LR Degrees
• Relative randomness and cardinality

This page was built for publication: Prompt enumerations and relative randomness

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