A DNC function that computes no effectively bi-immune set

DOI10.1007/S00153-015-0425-ZzbMATH Open1354.03054arXiv1308.1324OpenAlexW2159445998MaRDI QIDQ494640FDOQ494640

Authors: Achilles A. Beros 

Publication date: 1 September 2015

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

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.

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

Recommendations

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

zbMATH Keywords

degree theorycomputability theoryrecursion theoryDNCDNR

Mathematics Subject Classification ID

Other Turing degree structures (03D28)

Cites Work

• Title not available (Why is that?)
• Computability and Randomness
• Mass Problems and Randomness
• Title not available (Why is that?)
• Comparing DNR and WWKL
• Title not available (Why is that?)
• Diagonally non-computable functions and bi-immunity
• Solution to a Problem of Spector

Cited In (2)

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

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)