Abstract
Jockusch and Lewis (J Symb Logic 78:977–988, 2013) 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ambos-Spies K., Kjos-Hanssen B., Lempp S., Slaman T.: Comparing dnr and wwkl. J. Symb. Logic 69, 1089–1104 (2004)
Jockusch C.: Degrees of Functions with no Fixed Points. Elsevier B.V., North-Holland (1989)
Jockusch C., Lewis A.: Diagonally non-computable functions and bi-immunity. J. Symb. Logic 78, 977–988 (2013)
Kučera A.: An alternative, priority-free, solution to Post’s problem. Math. Found. Comput. Sci. 233, 493–500 (1986)
Lachlan A.: Solution to a problem of spector. Can. J. Math. 23, 247–256 (1971)
Muchnik A.: On the strong and weak reducibility of algorithmic problems. Sibirskii Matematicheskii Zhurnal 4, 1328–1341 (1971)
Nies A.: Computability and Randomness. Oxford University Press, Inc., New York (2009)
Simpson S.: Mass problems and randomness. Bull. Symb. Logic 11, 1–27 (2005)
Soare R.I.: Recursively enumerable sets and degrees: a study of computable functions and computably generated sets. Springer, New York (1987)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Beros, A.A. A DNC function that computes no effectively bi-immune set. Arch. Math. Logic 54, 521–530 (2015). https://doi.org/10.1007/s00153-015-0425-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-015-0425-z