On $$e$$-Principal and $$e$$-Complete Numberings
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.
Authors
- M. Kh. Faĭzrahmanov (ORCID: https://orcid.org/0000-0002-4519-9696)
Institutions
- Kazan Federal University (RU)
Publication Details
- Journal
- Mathematical Notes
- Published
- 2024-10-01
- DOI
- https://doi.org/10.1134/s000143462409013x
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00