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