Q-reducibility and m-reducibility on computably enumerable sets
Ilnur Ildarovich Batyrshin · Siberian Mathematical Journal · 2014
We study the distinctions between Q-reducibility and m-reducibility on computably enumerable sets. We construct a noncomputable m-incomplete computably enumerable set B such that all computably enumerable sets A ≤ Q B satisfy A ≤ m B. We prove that for every noncomputable computably enumerable set A there exists a computably enumerable set B such that A ≤ Q B but A ≰ m B. We prove that for every simple set B there exists a computably enumerable set A such that A ≤ Q B but A ≰ m B. The last result implies in particular that the Q-degree of every simple set contains infinitely many computably enumerable m-degrees.