|
Sibirskii Matematicheskii Zhurnal, 2014, Volume 55, Number 6, Pages 1221–1239
(Mi smj2600)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
$Q$-reducibility and $m$-reducibility on computably enumerable sets
I. I. Batyrshin Kazan (Volga Region) Federal University, Kazan, Russia
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.
Keywords:
$Q$-reducibility, $m$-reducibility, computably enumerable set, simple set.
Received: 27.11.2013
Citation:
I. I. Batyrshin, “$Q$-reducibility and $m$-reducibility on computably enumerable sets”, Sibirsk. Mat. Zh., 55:6 (2014), 1221–1239; Siberian Math. J., 55:6 (2014), 995–1008
Linking options:
https://www.mathnet.ru/eng/smj2600 https://www.mathnet.ru/eng/smj/v55/i6/p1221
|
|