Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






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


Matematicheskie Zametki, 2024, Volume 116, Issue 3, Pages 461–476
DOI: https://doi.org/10.4213/mzm14139
(Mi mzm14139)
 

On $e$-principal and $e$-complete numberings

M. Kh. Faizrahmanov

Kazan (Volga Region) Federal University
References:
Abstract: In the paper, generalizations of principal and complete numberings are studied, the so-called $e$-principal and $e$-complete numberings, respectively, that are consistent with the $e$-reducibility of numberings introduced by Degtev. It is proven that, for an arbitrary set $A$, every finite family of $A$-computably enumerable sets has an $A$-computable $e$-principal numbering. Necessary and sufficient conditions are obtained for the Turing completeness of the set $A$ in terms of $e$-principal and $e$-complete numberings of $A$-computable families. It is established that the classes of $e$-complete and precomplete numberings are not comparable with respect to inclusion, and also, for every Turing complete set $A$ and every infinite $A$-computable family, its $e$-complete $A$-computable numbering is constructed, which is both $e$-minimal and minimal.
Keywords: numbering, $e$-principal numbering, $e$-complete numbering, generalized computable numbering.
Funding agency Grant number
Russian Science Foundation 23-21-00181
Ministry of Science and Higher Education of the Russian Federation 075-02-2024-1438
This work was financially supported by the Russian Science Foundation, grant no. 23-21-00181, https://rscf.ru/en/project/23-21-00181/, and carried out as a part of the implementation of the development program of the Scientific and Educational Mathematical Center, Volga Federal District (agreement no. 075-02-2024-1438).
Received: 14.08.2023
Revised: 22.03.2024
English version:
Mathematical Notes, 2024, Volume 116, Issue 3, Pages 541–553
DOI: https://doi.org/10.1134/S000143462409013X
Document Type: Article
UDC: 510.5
MSC: 03D45
Language: Russian
Citation: M. Kh. Faizrahmanov, “On $e$-principal and $e$-complete numberings”, Mat. Zametki, 116:3 (2024), 461–476; Math. Notes, 116:3 (2024), 541–553
Citation in format AMSBIB
\Bibitem{Fai24}
\by M.~Kh.~Faizrahmanov
\paper On~$e$-principal and $e$-complete numberings
\jour Mat. Zametki
\yr 2024
\vol 116
\issue 3
\pages 461--476
\mathnet{http://mi.mathnet.ru/mzm14139}
\crossref{https://doi.org/10.4213/mzm14139}
\transl
\jour Math. Notes
\yr 2024
\vol 116
\issue 3
\pages 541--553
\crossref{https://doi.org/10.1134/S000143462409013X}
Linking options:
  • https://www.mathnet.ru/eng/mzm14139
  • https://doi.org/10.4213/mzm14139
  • https://www.mathnet.ru/eng/mzm/v116/i3/p461
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
    Statistics & downloads:
    Abstract page:66
    Russian version HTML:2
    References:17
    First page:7
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024