Contemporary Mathematics. Fundamental DirectionsContemporary Mathematics. Fundamental DirectionsСовременная математика. Фундаментальные направления2413-36392949-0618Peoples’ Friendship University of Russia named after Patrice Lumumba (RUDN University)3008010.22363/2413-3639-2021-67-4-707-754ArticlesСтатьиResearch ArticleSeparable Algorithmic Representations of Classical Systems and Their ApplicationsОтделимые алгоритмические представления классических систем и их приложенияKasymovN. Kh.КасымовН. Х.nadim59@mail.ruDadazhanovR. N.ДадажановР. Н.dadajonovrn@mail.ruIbragimovF. N.ИбрагимовФ. Н.farkh-i@yandex.comNational University of Uzbekistan named after M. UlugbekНациональный университет Узбекистана им. М. Улугбека30122021674Science — Technology — Education — Mathematics — MedicineНаука — технология — образование — математика — медицина70775424012022Copyright ©; 2022, Contemporary Mathematics. Fundamental DirectionsCopyright ©; 2022, Современная математика. Фундаментальные направления2022Contemporary Mathematics. Fundamental DirectionsСовременная математика. Фундаментальные направленияhttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.enhttps://journals.rudn.ru/CMFD/article/view/30080

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.

Излагаются основные результаты теории отделимых алгоритмических представлений классических алгебраических систем. Описываются важнейшие классы таких систем и их представления в нижних классах арифметической иерархии - позитивных и негативных. Особое внимание уделено алгоритмическим, структурным и топологическим свойствам отделимых представлений групп, колец и тел, а также эффективным аналогам теоремы А. И. Мальцева о вложимости колец в тела. Рассматриваются возможности применения изучаемых понятий в рамках теоретической информатики.

Биркгоф Г. Теория решеток. - М.: Наука, 1984.Гончаров С. С. Модели данных и языки их описаний// Вычисл. системы. - 1985. -107. - С. 52-70.Гончаров С. С., Ершов Ю. Л. Конструктивные модели. - Новосибирск: Научная книга, 1999.Ершов Ю. Л. Теория нумераций. - М.: Наука, 1977.Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. - М.: Наука, 1980.Касымов Н. Х. Алгебраическое описание рекурсивно перечислимых типов данных// Вычисл. системы. - 1984. -101. - С. 130-140.Касымов Н. Х. Логические программы без равенства и конструктивные представления// Вычисл. системы. - 1987. -122. - С. 3-18.Касымов Н. Х. Об алгебрах с финитно аппроксимируемыми позитивно представимыми обогащениями// Алгебра и логика. - 1987. -26, № 6. - С. 715-730.Касымов Н. Х. О неспецифицируемости эффективно представимых данных позитивными формулами// Докл. АН УзССР. - 1989. - № 6. - С. 4-5.Касымов Н. Х. Об одной двойственной задаче теории конструктивных моделей// Вычисл. системы. - 1989. -129. - С. 137-143.Касымов Н. Х. Финитная аппроксимируемость квазиэрбрановских моделей// Докл. АН УзССР. - 1989. - № 12. - С. 5-6.Касымов Н. Х. Позитивные модели и универсальные предложения// Вычисл. системы. - 1990. -133. - С. 3-13.Касымов Н. Х. Позитивные алгебры с конгруэнциями конечного индекса// Алгебра и логика. - 1991. - 30, № 3. - С. 293-305.Касымов Н. Х. Позитивные алгебры со счетными решетками конгруэнций// Алгебра и логика. - 1992. -31, № 1. - С. 21-37.Касымов Н. Х. Позитивные алгебры с нетеровыми решетками конгруэнций// Сиб. мат. ж. - 1992. - 33, № 2. - С. 181-185.Касымов Н. Х. О числе конгруэнций алгебр над простыми множествами// Мат. заметки. - 1992. -52, № 2. - С. 150-152.Касымов Н. Х. О гомоморфизмах на негативные алгебры// Алгебра и логика. - 1992. -31, № 2. - С. 132-144.Касымов Н. Х. О числе Q-конгруэнций позитивных алгебр// Алгебра и логика. - 1992. -31, № 3. - С. 297-305.Касымов Н. Х. О гомоморфизмах нумерованных алгебр с рекурсивно отделимыми классами// Докл. АН УзССР. - 1992. - № 6. - С. 3-4.Касымов Н. Х. Неконструктивные негативные алгебры с условиями конечности// Сиб. мат. ж. - 1992. -33, № 6. - С. 195-198.Касымов Н. Х. Совершенные нумерации алгебр// Узб. мат. ж. - 1993. - № 2. - С. 51-56.Касымов Н. Х. Аксиомы отделимости и разбиения натурального ряда// Сиб. мат. ж. - 1993. -34, № 3. - С. 81-85.Касымов Н. Х. Нумерованные алгебры с равномерно рекурсивно отделимыми классами// Сиб. мат. ж. - 1993. -34, № 5. - С. 85-102.Касымов Н. Х. Об алгебрах над негативными эквивалентностями// Алгебра и логика. - 1994. -33, № 1. - С. 76-80.Касымов Н. Х. Рекурсивно отделимые нумерованные алгебры// Усп. мат. наук. - 1996. -51, № 3. - С. 145-176.Касымов Н. Х. О полугруппах рекурсивных автоморфизмов нумерованных систем// Докл. АН РУз. - 1996. - № 12. - С. 3-4.Касымов Н. Х., Дадажанов Р. Н. О рекурсивно отделимых нумерациях, все рекурсивные автоморфизмы которых имеют неподвижные точки// Докл. АН РУз. - 2014. - № 1. - С. 5-7.Касымов Н. Х. О вычислимости негативных представлений стандартной модели арифметики Гончарова// Тез. докл. Межд. конф. «Алгебра, анализ и квантовая вероятность». - Ташкент, 2015. - С. 117-119.Касымов Н. Х., Дадажанов Р. Н. Позитивные и негативные линейные порядки и их вычислимо необратимые автоморфизмы// Вестн. НУУз. - 2015. - № 2. - С. 54-63.Касымов Н. Х. О точных представлениях линейных порядков над негативными эквивалентностями// Докл. АН РУз. - 2016. - № 1. - С. 9-12.Касымов Н. Х. О гомоморфизмах на эффективно отделимые алгебры// Сиб. мат. ж. - 2016. -57, № 1. - С. 47-66.Касымов Н. Х., Дадажанов Р. Н. Негативные плотные линейные порядки// Сиб. мат. ж. - 2017. -58, № 6. - С. 1306-1331.Касымов Н. Х., Дадажанов Р. Н. О вычислимости негативных представлений некоторых типов упорядоченных колец// Тез. докл. Межд. конф. «Алгебра и математическая логика: теория и приложения». - Казань, 2019. - С. 100-101.Касымов Н. Х., Ибрагимов Ф. Н. Структурная характеризация рекурсивно отделимых моделей// Докл. АН РУз. - 1998. - № 11. - С. 14-16.Касымов Н. Х., Ибрагимов Ф. Н. О негативности рекурсивно отделимых нумераций алгебр с артиновыми решетками конгруэнций// Докл. АН РУз. - 2013. - № 2. - С. 8-9.Касымов Н. Х., Ибрагимов Ф. Н. Сильно вычислимые нумерации и негативные эквивалентности// Докл. АН РУз. - 2014. - № 5. - С. 3-4.Касымов Н. Х., Ибрагимов Ф. Н. О непрерывности операций нумерованных алгебр в эффективно порожденных топологических пространствах// Докл. АН РУз. - 2016. - № 4. - С. 3-6.Касымов Н. Х., Ибрагимов Ф. Н. Вычислимо отделимые модели// Соврем. мат. Фундам. направл. - 2018. -64, № 4. - С. 682-705.Касымов Н. Х., Ибрагимов Ф. Н. Отделимые нумерации тел и эффективная вложимость в них колец// Сиб. мат. ж. - 2019. - 60, № 1. - С. 82-94.Касымов Н. Х., Куралов Ю. А. Вычислимость алгоритмических представлений упорядоченного кольца целых чисел// Вестн. НУУз. - 2017. - № 2. - С. 117-123.Касымов Н. Х., Морозов А. С. Логические программы без равенства и конструктивные представления// Вычисл. системы. - 1987. -122. - С. 73-96.Касымов Н. Х., Морозов А. С. Об определимости линейных порядков над негативными эквивалентностями// Алгебра и логика. - 2016. -55, № 1. - С. 37-57.Касымов Н. Х., Морозов А. С. О T1-отделимых нумерациях алгебр с артиновыми решетками конгруэнций// Тез. докл. Межд. конф. «Алгебра и математическая логика: теория и приложения». - Казань, 2019. - С. 118-120.Касымов Н. Х., Морозов А. С., Хо джамуратова И. А. О T1-отделимых нумерациях подпрямо неразложимых алгебр// Алгебра и логика. - 2021. -60, № 4. - С. 400-424.Касымов Н. Х., Хо джамуратова И. А. О компактных расширениях эффективных пространств// Докл. АН РУз. - 2017. - № 5. - С. 3-5.Касымов Н. Х., Хо джамуратова И. А. Топологические пространства над алгоритмическими представлениями универсальных алгебр// Итоги науки и техн. Соврем. пробл. мат. - 2018. -144. - С. 17-29.Касымов Н. Х., Хусаинов Б. М. Позитивные и негативные нумерации алгебр// Вычисл. системы. - 1991. -139. - С. 103-110.Касымов Н. Х., Хусаинов Б. М. Позитивные эквивалентности с конечными классами и алгебры над ними// Сиб. мат. ж. - 1992. -33, № 5. - С. 196-200.Кон П. М. Универсальная алгебра. - М.: Мир, 1968.Мальцев А. И. О вложении алгебраических колец в тела// Math. Ann. - 1937. -113. - С. 886-891.Мальцев А. И. К общей теории алгебраических систем// Мат. сб. - 1954. -35, № 1. - С. 3-20.Мальцев А. И. Конструктивные алгебры. I// Усп. мат. наук. - 1961. - 16, № 3. - С. 3-60.Мальцев А. И. Позитивные и негативные нумерации// Докл. АН СССР. - 1965. -160, № 2. - С. 278-280.Мальцев А. И. Алгебраические системы. - М.: Наука, 1970.Мальцев А. И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.Мартин-Леф П. Очерки по конструктивной математике. - М.: Мир, 1975.Ро джерс Х. Д. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.Соар Р. И. Вычислимо перечислимые множества и степени. - Казань: Казанское мат. об-во, 2000.Успенский В. А. О вычислимых операциях// Докл. АН СССР. - 1955. - 103, № 5. - С. 773-776.Успенский В. А. Системы перечислимых множеств и их нумерации// Докл. АН СССР. - 1955. -105, № 6. - С. 1155-1158.Baur W. Rekursive Algebren mit Kettenbedingungen// Z. Math. Logik Grundl. Math. - 1974. - 20. - С. 37-46.Baur W. Uber recursive strukturen// Invent. Math. - 1974. -23, № 2. - С. 89-95Bergstra J. A., Tucker J. V. A characterization of computable data types by means of a finite, equational specification method// Lecture Notes in Comput. Sci. - 1980. -85. - С. 76-90.Broy M., Dosch W., Partsch H., Pepper P., Wirsing M. Existential quantifiers in abstract data types// Lecture Notes in Comput. Sci. - 1979. -71. - С. 73-81.Feiner L. Hierarchies of Boolean algebras// J. Symbolic Logic. - 1970. - 35, № 2. - С. 365-373.Fokina E. B., Khoussainov B., Semukhin P., Turetskiy D. Linear orders realized by C.E. equivalence relations// J. Symbolic Logic. - 2016. -81, № 2. - С. 463-482.Kamin S. Some definitions for algebraic data type specifications// SIGPLAN Notes. - 1979. - 14, № 3. - С. 28-37.Kasymov N. Kh., Dadajanov R. N., Ibragimov F. N. On the negativity of Hausdorff algorithmic representations of translational complete algebras// Тез. докл. Межд. конф. «Современные проблемы математики и физики». - Ташкент, 2019. - С. 78-79.Kasymov N. Kh., Dadajanov R. N., Karimova N. R. Effective compacts over coimmunne sets// Uzb. Math. J. - 2019. - № 3. - С. 26-32.Khoussainov B., Slaman T., Semukhin P. Presentasions of algebras// Arch. Math. Logic. - 2006. - 45, № 6. - С. 769-781.Morozov A. S., Truss J. K. On computable automorphisms of the rational numbers// J. Symbolic Logic. - 2001. -66, № 3. - С. 1458-1470.Nerode A. General topology and partial recursive functionals// Summaries Summer Inst. Symbolic Logic. - 1960. - 1957. - С. 247-251.