Strong jump-traceability and Demuth randomness
From MaRDI portal
Publication:5411925
DOI10.1112/PLMS/PDT040zbMATH Open1303.03074arXiv1109.6128OpenAlexW1980688886MaRDI QIDQ5411925FDOQ5411925
Daniel Turetsky, Noam Greenberg
Publication date: 25 April 2014
Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1109.6128
Recommendations
Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)
Cited In (13)
- On strongly jump traceable reals
- Strong Medvedev reducibilities and the KL-randomness problem
- Martin-Löf reducibility and cost functions
- Calculus of cost functions
- Superhighness and Strong Jump Traceability
- STRONG JUMP-TRACEABILITY
- JSL volume 79 issue 2 Cover and Front matter
- Strong jump-traceability. I: The computably enumerable case
- Demuth's path to randomness
- Inherent enumerability of strong jump-traceability
- Characterizing the strongly jump-traceable sets via randomness
- Computability theory. Abstracts from the workshop held January 7--13, 2018
- ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY
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)
