Sibirskii Matematicheskii Zhurnal
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Full-text PDF (415 kB) Citations (3)
References:
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
English version:
Siberian Mathematical Journal, 2014, Volume 55, Issue 6, Pages 995–1008
DOI: https://doi.org/10.1134/S0037446614060032
Bibliographic databases:
Document Type: Article
UDC: 510.5
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Bat14}
\by I.~I.~Batyrshin
\paper $Q$-reducibility and $m$-reducibility on computably enumerable sets
\jour Sibirsk. Mat. Zh.
\yr 2014
\vol 55
\issue 6
\pages 1221--1239
\mathnet{http://mi.mathnet.ru/smj2600}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3330031}
\transl
\jour Siberian Math. J.
\yr 2014
\vol 55
\issue 6
\pages 995--1008
\crossref{https://doi.org/10.1134/S0037446614060032}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000346495200003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84919423115}
Linking options:
  • https://www.mathnet.ru/eng/smj2600
  • https://www.mathnet.ru/eng/smj/v55/i6/p1221
  • This publication is cited in the following 3 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Сибирский математический журнал Siberian Mathematical Journal
    Statistics & downloads:
    Abstract page:229
    Full-text PDF :108
    References:53
    First page:7
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024