Strong jump-traceability and Demuth randomness

DOI10.1112/PLMS/PDT040MaRDI QIDQ5411925zbMATH OpenOpenAlexFDO

Authors Noam Greenberg, Daniel Turetsky

Publication date 25 April 2014

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Demuth randomnessstrong jump-traceability

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)

Abstract: We solve the covering problem for Demuth randomness, showing that a computably enumerable set is computable from a Demuth random set if and only if it is strongly jump-traceable. We show that on the other hand, the class of sets which form a base for Demuth randomness is a proper subclass of the class of strongly jump-traceable sets.

Recommendations

• Computably enumerable sets below random sets
• Demuth randomness and computational complexity
• A random set which only computes strongly jump-traceable c.e. sets
• Characterizing lowness for Demuth randomness
• Strong jump-traceability

Cited in

(15)

• On the interplay between effective notions of randomness and genericity
• Strong jump-traceability
• Characterizing the strongly jump-traceable sets via randomness
• Inherent enumerability of strong jump-traceability
• Calculus of cost functions
• Demuth randomness and computational complexity
• Computability theory. Abstracts from the workshop held January 7--13, 2018
• On strongly jump traceable reals
• Strong jump-traceability. I: The computably enumerable case
• JSL volume 79 issue 2 Cover and Front matter
• A random set which only computes strongly jump-traceable c.e. sets
• Strong Medvedev reducibilities and the KL-randomness problem
• Demuth's path to randomness
• Superhighness and Strong Jump Traceability
• Martin-Löf reducibility and cost functions

This page was built for publication: Strong jump-traceability and Demuth randomness

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