On a generic Turing reducibility of computably enumerable sets
Alexander Rybalov · Journal of Physics Conference Series · 2019
Kapovich, Myasnikov, Schupp and Shpilrain in 2003 developed generic approach to algorithmic problems, which considers an algorithmic problem on "most" of the inputs (i.e., on a generic set) instead of the entire domain and ignores it on the rest of inputs (a negligible set). Jockusch and Schupp in 2012 defined a generic analog of Turing reducibility. In this paper we investigate a generic reducibility of computably enumerable (c.e.) sets. We prove that there exists a pair of incomparable c.e. sets, that there is a complete c.e. set, that there are no minimal and maximal c.e. sets. Also we prove some analog of classical Sacks density theorem. Supported by Russian Science Foundation, grant 18-71-10028.