|
This article is cited in 4 scientific papers (total in 4 papers)
On $p$-universal and $p$-minimal numberings
M. Kh. Faizrahmanov Kazan (Volga Region) Federal University
Abstract:
We study the $p$-reducibility of numberings which was introduced and first studied by Degtev. $p$-Reducibility is an effectively bounded version of the $e$-reducibility of numberings. Also, we prove that for every set $A$ there exists an $A$-computable family without universal numberings but admitting $p$-universal numberings and obtain a criterion for the existence of $p$-universal numberings of finite families of $A$-c.e. sets. Finally, we show that every $A$-computable family, with $\emptyset''\leq _TA$, has infinitely many pairwise non-$p$-equivalent $p$-minimal $A$-computable numberings.
Keywords:
computable numbering, $A$-computable numbering, $p$-reducibility, universal numbering, $p$-universal numbering, $p$-minimal numbering.
Received: 31.03.2021 Revised: 31.03.2021 Accepted: 10.12.2021
Citation:
M. Kh. Faizrahmanov, “On $p$-universal and $p$-minimal numberings”, Sibirsk. Mat. Zh., 63:2 (2022), 427–436; Siberian Math. J., 63:2 (2022), 365–373
Linking options:
https://www.mathnet.ru/eng/smj7667 https://www.mathnet.ru/eng/smj/v63/i2/p427
|
Statistics & downloads: |
Abstract page: | 103 | Full-text PDF : | 35 | References: | 29 | First page: | 5 |
|