|
Sibirskii Matematicheskii Zhurnal, 2022, Volume 63, Number 2, Pages 427–436 DOI: https://doi.org/10.33048/smzh.2022.63.213
(Mi smj7667)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
On $p$-universal and $p$-minimal numberings
M. Kh. Faizrahmanov Kazan (Volga Region) Federal University
DOI:
https://doi.org/10.33048/smzh.2022.63.213
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
|
|