On a General Method of Constructing Post Reducibilities and the Corresponding Completeness Criteria
M. M. Arslanov · Lobachevskii Journal of Mathematics · 2022
Abstract In computability theory the most common form of reducibility is Turing reducibility. Earlier, the author found necessary and sufficient conditions for the completeness of computably enumerable sets for this reducibility. Later, this criterion was generalized by various authors to new classes of functions, and also investigated for some of the most important reducibilities, stronger than Turing reducibility. In this paper, we discuss one general method for constructing similar criteria for a wide class of reducibility.