|
This article is cited in 1 scientific paper (total in 1 paper)
Minimal generalized computable numberings and families of positive preorders
F. Rakymzhankyzya, N. A. Bazhenovb, A. A. Issakhova, B. S. Kalmurzayevca a Kazakh-British Technical University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
c Al-Farabi Kazakh National University
Abstract:
We study $A$-computable numberings for various natural classes of sets. For an arbitrary oracle $A\geq_T \mathbf{0'}$, an example of an $A$-computable family $S$ is constructed in which each $A$-computable numbering of $S$ has a minimal cover, and at the same time, $S$ does not satisfy the sufficient conditions for the existence of minimal covers specified by S. A. Badaev and S. Yu. Podzorov in [Sib. Math. J., 43, No. 4, 616–622 (2002)]. It is proved that the family of all positive linear preorders has an $A$-computable numbering iff $A' \geq_T \mathbf{0}''$. We obtain a series of results on minimal $A$-computable numberings, in particular, Friedberg numberings and positive undecidable numberings.
Keywords:
$A$-computable numbering, positive linear preorder, Rogers semilattice, Friedberg numbering, positive numbering, minimal cover.
Received: 03.11.2021 Revised: 28.10.2022
Citation:
F. Rakymzhankyzy, N. A. Bazhenov, A. A. Issakhov, B. S. Kalmurzayev, “Minimal generalized computable numberings and families of positive preorders”, Algebra Logika, 61:3 (2022), 280–307
Linking options:
https://www.mathnet.ru/eng/al2711 https://www.mathnet.ru/eng/al/v61/i3/p280
|
Statistics & downloads: |
Abstract page: | 112 | Full-text PDF : | 47 | References: | 19 |
|