Abstract:
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\le_QB$ satisfy $A\le_mB$. We prove that for every noncomputable computably enumerable set $A$ there exists a computably enumerable set $B$ such that $A\le_QB$ but $A\not\le_mB$. We prove that for every simple set $B$ there exists a computably enumerable set $A$ such that $A\le_QB$ but $A\not\le_mB$. The last result implies in particular that the $Q$-degree of every simple set contains infinitely many computably enumerable $m$-degrees.