Covering the Recursive Sets

DOI10.1007/978-3-319-20028-6_5MaRDI QIDQ3195679zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen, Sebastiaan A. Terwijn, Frank Stephan

Publication date 20 October 2015

Published in Evolving Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.05875, http://hdl.handle.net/2066/147448

Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Descriptive set theory (03E15)

Abstract: We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Covering the Recursive Sets

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