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.
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).