A DNC function that computes no effectively bi-immune set

DOI10.1007/S00153-015-0425-ZMaRDI QIDQ494640zbMATHOpenAlexFDO

Authors Achilles A. Beros

Publication date 1 September 2015

Published in Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

degree theorycomputability theoryrecursion theoryDNCDNR

Mathematics Subject Classification ID

Other Turing degree structures (03D28)

Abstract: In Diagonally Non-Computable Functions and Bi-Immunity, Carl Jockusch and Andrew Lewis proved that every DNC function computes a bi-immune set. They asked whether every DNC function computes an effectively bi-immune set. We construct a DNC function that computes no effectively bi-immune set, thereby answering their question in the negative.

Recommendations

• scientific article; zbMATH DE number 3859105
• Joining non-low C.E. sets with diagonally non-computable functions
• scientific article; zbMATH DE number 4135927
• scientific article; zbMATH DE number 4004170
• Effective bi-immunity and randomness

Cites work

• scientific article; zbMATH DE number 4135927 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3995657 (Why is no real title available?)
• Comparing DNR and WWKL
• Computability and Randomness
• Diagonally non-computable functions and bi-immunity
• Mass Problems and Randomness
• Solution to a Problem of Spector

Cited in

(2)

• Effective bi-immunity and randomness
• Forcing with bushy trees

This page was built for publication: A DNC function that computes no effectively bi-immune set

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