RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2014 Volume 55, Number 6, Pages 1221–1239 (Mi smj2600)

This article is cited 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.

UDC: 510.5

Received: 27.11.2013


 English version:
Siberian Mathematical Journal, 2014, 55:6, 995–1008

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024