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

M. Kh. Faizrahmanov

Matematičeskie zametki, Tome 116 (2024) no. 3, pp. 461-476

Résumé

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.

Détail

Keywords: numbering, $e$-principal numbering, $e$-complete numbering, generalized computable numbering.

Bibliographie

[1] V. A. Uspenskii, A. L. Semenov, Teoriya algoritmov: osnovnye otkrytiya i prilozheniya, Nauka, M., 1987 | MR

[2] V. A. Uspenskii, “Kolmogorov, kakim ya ego pomnyu”, Kolmogorov v vospominaniyakh uchenikov, eds. A. N. Shiryaev, MTsNMO, M., 2006, 272–371 | MR

[3] V. A. Uspenskii, “Neskolko zamechanii o perechislimykh mnozhestvakh”, Z. Math. Logik Grundlagen Math., 3:12 (1957), 157–170 | DOI | MR

[4] V. A. Uspenskii, Lektsii o vychislimykh funktsiyakh, Fizmatgiz, M., 1960 | MR

[5] V. A. Uspenskii, “O svodimosti vychislimykh i potentsialno vychislimykh numeratsii”, Matem. zametki, 6:1 (1969), 3–9 | MR | Zbl

[6] A. I. Maltsev, “Konstruktivnye algebry. I”, UMN, 16:3 (99) (1961), 3–60 | MR | Zbl

[7] A. I. Maltsev, “Polno numerovannye mnozhestva”, Algebra i logika. Seminar, 2:2 (1963), 4–29 | MR

[8] A. I. Maltsev, Algoritmy i rekursivnye funktsii, Nauka, M., 1965 | MR

[9] Yu. L. Ershov, “Numeratsiya semeistv obscherekursivnykh funktsii”, Sib. matem. zhurn., 8:5 (1967), 1015–1025 | MR | Zbl

[10] Yu. L. Ershov, “Polno numerovannye mnozhestva”, Sib. matem. zhurn., 10:5 (1969), 1048–1064 | MR | Zbl

[11] Yu. L. Ershov, “O neotdelimykh parakh”, Algebra i logika, 9:6 (1970), 661–666 | MR

[12] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[13] Yu. L. Ershov, “Theory of numberings”, Handbook of Computability Theory, Stud. Logic Found. Math., 140, ed. E. R. Griffor, Elsevier, Amsterdam, 1999, 473–503 | MR

[14] Yu. L. Ershov, Opredelimost i vychislimost, Nauchnaya kniga, Novosibirsk, 1996 | MR

[15] S. S. Goncharov, A. Sorbi, “Obobschenno-vychislimye numeratsii i trivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR

[16] S. A. Badaev, S. S. Goncharov, “O polureshetkakh Rodzhersa semeistv arifmeticheskikh mnozhestv”, Algebra i logika, 40:5 (2001), 507–522 | MR | Zbl

[17] S. A. Badaev, S. Yu. Podzorov, “Minimalnye nakrytiya v polureshetkakh Rodzhersa $\Sigma_n^0$-vychislimykh numeratsii”, Sib. matem. zhurn., 43:4 (2002), 769–778 | MR | Zbl

[18] S. Yu. Podzorov, “O lokalnom stroenii polureshetok Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Algebra i logika, 44:2 (2005), 148–172 | MR | Zbl

[19] S. A. Badaev, S. S. Goncharov, “Computability and numberings”, New Computational Paradigms, Springer-Verlag, New York, NY, 2008, 19–34 | MR

[20] M. Kh. Faizrakhmanov, “O teoreme Khutoretskogo dlya obobschenno vychislimykh semeistv”, Algebra i logika, 58:4 (2019), 528–541 | DOI

[21] S. A. Badaev, S. S. Goncharov, “Obobschenno vychislimye universalnye numeratsii”, Algebra i logika, 53:5 (2014), 555–569 | MR

[22] M. Kh. Faizrakhmanov, “O polureshetkakh Rodzhersa obobschenno vychislimykh numeratsii”, Sib. matem. zhurn., 58:6 (2017), 1418–1427 | DOI

[23] S. A. Badaev, A. A. Isakhov, “Nekotorye absolyutnye svoistva $A$-vychislimykh numeratsii”, Algebra i logika, 57:4 (2018), 426–447 | DOI

[24] F. Rakymzhankyzy, N. A. Bazhenov, A. A. Isakhov, B. S. Kalmurzaev, “Minimalnye obobschenno vychislimye numeratsii i semeistva pozitivnykh predporyadkov”, Algebra i logika, 61:3 (2022), 280–307 | DOI | MR

[25] A. N. Degtev, “O svodimostyakh numeratsii”, Matem. sb., 112 (154):2 (6) (1980), 207–219 | MR | Zbl

[26] S. Jain, J. Nessel, “Some independence results for control structures in complete numberings”, J. Symbolic Logic, 66:1 (2001), 357–382 | DOI | MR

[27] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Completeness and universality of arithmetical numberings”, Computability and Models, Univ. Ser. Math., Springer, Boston, MA, 2003, 11–44 | MR

[28] M. Faizrahmanov, “Extremal numberings and fixed point theorems”, MLQ Math. Log. Q., 68:4 (2022), 398–408 | DOI | MR

[29] M. Kh. Faizrakhmanov, “Pozitivnye svodimosti, ekstremalnye numeratsii i polnota”, Matem. tr., 26:1 (2023), 176–191 | MR

[30] R. I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets, Perspect. Math. Logic, Springer-Verlag, Berlin, 1987 | MR

[31] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR

[32] M. Kh. Faizrakhmanov, “Svodimost po perechislimosti i pozitivnaya svodimost numeratsii semeistv arifmeticheskikh mnozhestv”, Sib. matem. zhurn., 64:1 (2023), 204–212 | DOI | MR

[33] A. N. Degtev, M. L. Platonov, “O $e$-glavnykh numeratsiyakh”, Sib. matem. zhurn., 49:2 (2008), 299–307 | MR | Zbl

[34] A. N. Degtev, “Ob odnoi kategorii numerovannykh mnozhestv”, Matem. zametki, 36:2 (1984), 261–268 | MR | Zbl

[35] M. Kh. Faizrakhmanov, “Universalnye obobschenno vychislimye numeratsii i giperimmunnost”, Algebra i logika, 56:4 (2017), 506–521 | DOI | MR