RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2024 Volume 116, Issue 3, Pages 461–476 (Mi mzm14139)

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

M. Kh. Faizrahmanov

Kazan (Volga Region) Federal University

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.

UDC: 510.5

MSC: 03D45

Received: 14.08.2023
Revised: 22.03.2024

DOI: 10.4213/mzm14139


 English version:
Mathematical Notes, 2024, 116:3, 541–553


© Steklov Math. Inst. of RAS, 2024