Separable algorithmic representations of classical systems and their applications

N. Kh. Kasymov ; R. N. Dadazhanov ; F. N. Ibragimov

Contemporary Mathematics. Fundamental Directions, Science — Technology — Education — Mathematics — Medicine, Tome 67 (2021) no. 4, pp. 707-754.

Résumé

The main results of the theory of separable algorithmic representations of classical algebraic systems are presented. The most important classes of such systems and their representations in the lower classes of the arithmetic hierarchy — positive and negative — are described. Special attention is paid to the algorithmic, structural and topological properties of separable representations of groups, rings and bodies, as well as to effective analogs of the Maltsev theorem on embedding rings in bodies. The possibilities of using the studied concepts in the framework of theoretical informatics are considered.

Bibliographie

[1] Birkgof G., Teoriya reshetok, Nauka, M., 1984

[2] Goncharov S. S., “Modeli dannykh i yazyki ikh opisanii”, Vychisl. sistemy, 107 (1985), 52–70 | Zbl

[3] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999

[4] Ershov Yu. L., Teoriya numeratsii, Nauka, M., 1977

[5] Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980

[6] Kasymov N. Kh., “Algebraicheskoe opisanie rekursivno perechislimykh tipov dannykh”, Vychisl. sistemy, 101 (1984), 130–140 | Zbl

[7] Kasymov N. Kh., “Logicheskie programmy bez ravenstva i konstruktivnye predstavleniya”, Vychisl. sistemy, 122 (1987), 3–18 | Zbl

[8] Kasymov N. Kh., “Ob algebrakh s finitno approksimiruemymi pozitivno predstavimymi obogascheniyami”, Algebra i logika, 26:6 (1987), 715–730 | MR

[9] Kasymov N. Kh., “O nespetsifitsiruemosti effektivno predstavimykh dannykh pozitivnymi formulami”, Dokl. AN UzSSR, 1989, no. 6, 4–5 | Zbl

[10] Kasymov N. Kh., “Ob odnoi dvoistvennoi zadache teorii konstruktivnykh modelei”, Vychisl. sistemy, 129 (1989), 137–143 | Zbl

[11] Kasymov N. Kh., “Finitnaya approksimiruemost kvazierbranovskikh modelei”, Dokl. AN UzSSR, 1989, no. 12, 5–6

[12] Kasymov N. Kh., “Pozitivnye modeli i universalnye predlozheniya”, Vychisl. sistemy, 133 (1990), 3–13 | Zbl

[13] Kasymov N. Kh., “Pozitivnye algebry s kongruentsiyami konechnogo indeksa”, Algebra i logika, 30:3 (1991), 293–305 | MR

[14] Kasymov N. Kh., “Pozitivnye algebry so schetnymi reshetkami kongruentsii”, Algebra i logika, 31:1 (1992), 21–37 | MR | Zbl

[15] Kasymov N. Kh., “Pozitivnye algebry s neterovymi reshetkami kongruentsii”, Sib. mat. zh., 33:2 (1992), 181–185 | MR | Zbl

[16] Kasymov N. Kh., “O chisle kongruentsii algebr nad prostymi mnozhestvami”, Mat. zametki, 52:2 (1992), 150–152

[17] Kasymov N. Kh., “O gomomorfizmakh na negativnye algebry”, Algebra i logika, 31:2 (1992), 132–144 | MR | Zbl

[18] Kasymov N. Kh., “O chisle Q-kongruentsii pozitivnykh algebr”, Algebra i logika, 31:3 (1992), 297–305 | MR | Zbl

[19] Kasymov N. Kh., “O gomomorfizmakh numerovannykh algebr s rekursivno otdelimymi klassami”, Dokl. AN UzSSR, 1992, no. 6, 3–4

[20] Kasymov N. Kh., “Nekonstruktivnye negativnye algebry s usloviyami konechnosti”, Sib. mat. zh., 33:6 (1992), 195–198 | MR

[21] Kasymov N. Kh., “Sovershennye numeratsii algebr”, Uzb. mat. zh., 1993, no. 2, 51–56

[22] Kasymov N. Kh., “Aksiomy otdelimosti i razbieniya naturalnogo ryada”, Sib. mat. zh., 34:3 (1993), 81–85 | MR | Zbl

[23] Kasymov N. Kh., “Numerovannye algebry s ravnomerno rekursivno otdelimymi klassami”, Sib. mat. zh., 34:5 (1993), 85–102 | MR | Zbl

[24] Kasymov N. Kh., “Ob algebrakh nad negativnymi ekvivalentnostyami”, Algebra i logika, 33:1 (1994), 76–80 | MR | Zbl

[25] Kasymov N. Kh., “Rekursivno otdelimye numerovannye algebry”, Usp. mat. nauk, 51:3 (1996), 145–176 | MR | Zbl

[26] Kasymov N. Kh., “O polugruppakh rekursivnykh avtomorfizmov numerovannykh sistem”, Dokl. AN RUz, 1996, no. 12, 3–4 | Zbl

[27] Kasymov N. Kh., Dadazhanov R. N., “O rekursivno otdelimykh numeratsiyakh, vse rekursivnye avtomorfizmy kotorykh imeyut nepodvizhnye tochki”, Dokl. AN RUz, 2014, no. 1, 5–7

[28] Kasymov N. Kh., “O vychislimosti negativnykh predstavlenii standartnoi modeli arifmetiki Goncharova”, Tez. dokl. Mezhd. konf. «Algebra, analiz i kvantovaya veroyatnost» (Tashkent, 2015), 117–119

[29] Kasymov N. Kh., Dadazhanov R. N., “Pozitivnye i negativnye lineinye poryadki i ikh vychislimo neobratimye avtomorfizmy”, Vestn. NUUz, 2015, no. 2, 54–63

[30] Kasymov N. Kh., “O tochnykh predstavleniyakh lineinykh poryadkov nad negativnymi ekvivalentnostyami”, Dokl. AN RUz, 2016, no. 1, 9–12

[31] Kasymov N. Kh., “O gomomorfizmakh na effektivno otdelimye algebry”, Sib. mat. zh., 57:1 (2016), 47–66 | MR | Zbl

[32] Kasymov N. Kh., Dadazhanov R. N., “Negativnye plotnye lineinye poryadki”, Sib. mat. zh., 58:6 (2017), 1306–1331 | MR | Zbl

[33] Kasymov N. Kh., Dadazhanov R. N., “O vychislimosti negativnykh predstavlenii nekotorykh tipov uporyadochennykh kolets”, Tez. dokl. Mezhd. konf. «Algebra i matematicheskaya logika: teoriya i prilozheniya» (Kazan, 2019), 100–101

[34] Kasymov N. Kh., Ibragimov F. N., “Strukturnaya kharakterizatsiya rekursivno otdelimykh modelei”, Dokl. AN RUz, 1998, no. 11, 14–16

[35] Kasymov N. Kh., Ibragimov F. N., “O negativnosti rekursivno otdelimykh numeratsii algebr s artinovymi reshetkami kongruentsii”, Dokl. AN RUz, 2013, no. 2, 8–9

[36] Kasymov N. Kh., Ibragimov F. N., “Silno vychislimye numeratsii i negativnye ekvivalentnosti”, Dokl. AN RUz, 2014, no. 5, 3–4

[37] Kasymov N. Kh., Ibragimov F. N., “O nepreryvnosti operatsii numerovannykh algebr v effektivno porozhdennykh topologicheskikh prostranstvakh”, Dokl. AN RUz, 2016, no. 4, 3–6

[38] Kasymov N. Kh., Ibragimov F. N., “Vychislimo otdelimye modeli”, Sovrem. mat. Fundam. napravl., 64, no. 4, 2018, 682–705

[39] Kasymov N. Kh., Ibragimov F. N., “Otdelimye numeratsii tel i effektivnaya vlozhimost v nikh kolets”, Sib. mat. zh., 60:1 (2019), 82–94 | MR | Zbl

[40] Kasymov N. Kh., Kuralov Yu. A., “Vychislimost algoritmicheskikh predstavlenii uporyadochennogo koltsa tselykh chisel”, Vestn. NUUz, 2017, no. 2, 117–123

[41] Kasymov N. Kh., Morozov A. S., “Logicheskie programmy bez ravenstva i konstruktivnye predstavleniya”, Vychisl. sistemy, 122 (1987), 73–96 | Zbl

[42] Kasymov N. Kh., Morozov A. S., “Ob opredelimosti lineinykh poryadkov nad negativnymi ekvivalentnostyami”, Algebra i logika, 55:1 (2016), 37–57 | MR | Zbl

[43] Kasymov N. Kh., Morozov A. S., “O $T_1$-otdelimykh numeratsiyakh algebr s artinovymi reshetkami kongruentsii”, Tez. dokl. Mezhd. konf. «Algebra i matematicheskaya logika: teoriya i prilozheniya» (Kazan, 2019), 118–120

[44] Kasymov N. Kh., Morozov A. S., Khodzhamuratova I. A., “O $T_1$-otdelimykh numeratsiyakh podpryamo nerazlozhimykh algebr”, Algebra i logika, 60:4 (2021), 400–424 | Zbl

[45] Kasymov N. Kh., Khodzhamuratova I. A., “O kompaktnykh rasshireniyakh effektivnykh prostranstv”, Dokl. AN RUz, 2017, no. 5, 3–5

[46] Kasymov N. Kh., Khodzhamuratova I. A., “Topologicheskie prostranstva nad algoritmicheskimi predstavleniyami universalnykh algebr”, Itogi nauki i tekhn. Sovrem. probl. mat., 144, 2018, 17–29 | MR

[47] Kasymov N. Kh., Khusainov B. M., “Pozitivnye i negativnye numeratsii algebr”, Vychisl. sistemy, 139 (1991), 103–110 | Zbl

[48] Kasymov N. Kh., Khusainov B. M., “Pozitivnye ekvivalentnosti s konechnymi klassami i algebry nad nimi”, Sib. mat. zh., 33:5 (1992), 196–200 | MR | Zbl

[49] Kon P. M., Universalnaya algebra, Mir, M., 1968

[50] Maltsev A. I., “O vlozhenii algebraicheskikh kolets v tela”, Math. Ann., 113 (1937), 886–891

[51] Maltsev A. I., “K obschei teorii algebraicheskikh sistem”, Mat. sb., 35:1 (1954), 3–20 | Zbl

[52] Maltsev A. I., “Konstruktivnye algebry. I”, Usp. mat. nauk, 16:3 (1961), 3–60 | MR | Zbl

[53] Maltsev A. I., “Pozitivnye i negativnye numeratsii”, Dokl. AN SSSR, 160:2 (1965), 278–280 | Zbl

[54] Maltsev A. I., Algebraicheskie sistemy, Nauka, M., 1970

[55] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1986

[56] Martin-Lef P., Ocherki po konstruktivnoi matematike, Mir, M., 1975

[57] Rodzhers Kh. D., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[58] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni, Kazanskoe mat. ob-vo, Kazan, 2000

[59] Uspenskii V. A., “O vychislimykh operatsiyakh”, Dokl. AN SSSR, 103:5 (1955), 773–776 | Zbl

[60] Uspenskii V. A., “Sistemy perechislimykh mnozhestv i ikh numeratsii”, Dokl. AN SSSR, 105:6 (1955), 1155–1158 | Zbl

[61] Baur W., “Rekursive Algebren mit Kettenbedingungen”, Z. Math. Logik Grundl. Math., 20 (1974), 37–46 | DOI | Zbl

[62] Baur W., “Uber recursive strukturen”, Invent. Math., 23:2 (1974), 89–95 | DOI | MR | Zbl

[63] Bergstra J. A., Tucker J. V., “A characterization of computable data types by means of a finite, equational specification method”, Lecture Notes in Comput. Sci., 85, 1980, 76–90 | DOI | Zbl

[64] Broy M., Dosch W., Partsch H., Pepper P., Wirsing M., “Existential quantifiers in abstract data types”, Lecture Notes in Comput. Sci., 71, 1979, 73–81 | DOI

[65] Feiner L., “Hierarchies of Boolean algebras”, J. Symbolic Logic, 35:2 (1970), 365–373 | DOI | MR

[66] Fokina E. B., Khoussainov B., Semukhin P., Turetskiy D., “Linear orders realized by C.E. equivalence relations”, J. Symbolic Logic, 81:2 (2016), 463–482 | DOI | MR | Zbl

[67] Kamin S., “Some definitions for algebraic data type specifications”, SIGPLAN Notes, 14:3 (1979), 28–37 | DOI | MR

[68] Kasymov N. Kh., Dadajanov R. N., Ibragimov F. N., “On the negativity of Hausdorff algorithmic representations of translational complete algebras”, Tez. dokl. Mezhd. konf. «Sovremennye problemy matematiki i fiziki» (Tashkent, 2019), 78–79

[69] Kasymov N. Kh., Dadajanov R. N., Karimova N. R., “Effective compacts over coimmunne sets”, Uzb. Math. J., 2019, no. 3, 26–32 | MR | Zbl

[70] Khoussainov B., Slaman T., Semukhin P., “$\prod\limits_1^0$-presentasions of algebras”, Arch. Math. Logic, 45:6 (2006), 769–781 | DOI | MR | Zbl

[71] Morozov A. S., Truss J. K., “On computable automorphisms of the rational numbers”, J. Symbolic Logic, 66:3 (2001), 1458–1470 | DOI | MR | Zbl

[72] Nerode A., “General topology and partial recursive functionals”, Summaries Summer Inst. Symbolic Logic, 1957 (1960), 247–251 | Zbl