Loading [MathJax]/jax/output/CommonHTML/jax.js
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:135
    Full-text PDF :1
    Russian version HTML:3
    References:28
    First page:8
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025