chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2023-24-1-40-49cheb-1472Research ArticleСтатьиArticleПроблема разрешимости позитивной теории произвольной группы алгоритмически неразрешимаThe problem of solvability of a positive theory of an arbitrary group is algorithmically unsolvableДурневВалерий ГеоргиевичDurnevValeriy Georgievichdurnev@uniyar.ac.ruЗеткинаАлена ИгоревнаZetkinaAlena IgorevnaЯрославский государственный университет им. П. Г. ДемидоваРоссияYaroslavl State UniversityRussian FederationЯрославский государственный университет им. П. Г. Демидова; Воронежский государственный университетРоссияYaroslavl State University; Voroneg State UniversityRussian Federation2023240520232414049Copyright © Дурнев В.Г., Зеткина А.И., 20232023Дурнев В.Г., Зеткина А.И.Durnev V.G., Zetkina A.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1472

В статье доказано, что невозможно построить алгоритм, позволяющий по произвольному конечному заданию группы определить, разрешима ли ее позитивная теория. Указанноегрупповое свойство не является марковским, поэтому к нему не применима фундаментальная теорема Адяна – Рабина.

In paper proved that it is impossible to build an algorithm that allows you to determine from an arbitrary finite task of the group whether it is solvable her positive theory. The specified group property is not Markov, so the fundamental Adyan-Rabin theorem does not apply to it.

позитивная формулапозитивная теория группыпозитивная теория класса группалгоритмическая разрешимостьалгоритмическая неразрешимость.positive formulapositive group theorypositive group class theoryalgorithmic solvabilityalgorithmic insolubility.Работа выполнена при финансовой поддержке РФФИ (проект № 19 - 52 - 26006).ReferencesАдян С. И. Алгоритмическая неразрешимость проблем распознавания некоторых свойствAdyan, S, I. 1955, “Algorithmic intractable problems of recognizing some properties of groups”,групп // Докл. АН СССР. 1955. Т. 103, № 4. С. 533–535.Dokl. USSR ACADEMY OF SCIENCES, vol. 103, no. 4, pp. 533-535.Адян С. И. Неразрешимость некоторых алгоритмических проблем теории групп // ТрудыAdyan, S, I. 1957, “Insolubility of some algorithmic problems of group theory”, Works of MMO,ММО. 1957. Т. 6. С. 231-298.vol. 6. pp. 231-298.Rabin M. O. Recursive unsolvability of group theoretic problems // Ann. of Math. 1958. Vol. 67,Rabin M. O. 1958, “Recursive unsolvability of group theoretic problems”, Ann. of Math., vol. 67,№ 1. P. 172-194.no. 1, pp. 172-194.Collings D. J. On recognizing Hopf groups // Arh. Math. 1969. Vol. 20. P. 235-240.Collings D. J. 1992, “On recognizing Hopf groups”, Arh. Math., vol. 20, pp. 235-240.Miller C. F. III. Decision problems for groups – servey and reflections // Math. Sci. Res. Inst.Miller C. F. III. 1992, “Decision problems for groups – servey and reflections”, Math. Sci. Res.Publ. 1992. Vol. 23. P. 1-59.Inst. Publ., vol. 23, pp. 1-59.Miller C. F. III, Schupp P.E. Embeddings into Hopfian groups // Journal Algebra, 1971. Vol. 17.Miller C. F. III & Schupp P.E. 1971, “Embeddings into Hopfian groups”, Journal Algebra,P. 171-176.vol. 17, pp. 171-176.Miller C. F. III. On group-theoretic decision problems and their classification // Ann. of Math.Miller C. F. III. 1966, “On group-theoretic decision problems and their classification”, Ann. ofStudies. 1971. Vol. 68. Princeton University Press.Math. Studies, vol. 68. Princeton University Press.Мерзляков Ю. И. Позитивные формулы на свободных группах. // Алгебра и логика. 1966.Merzlyakov Yu. I. 1966, “Positive formulas on free groups”, Algebra and logic, vol. 5, issue 4.Т. 5, вып. 4. С. 25-42.pp. 25-42.Sacerdote G. S. Almost all free products of groups have the same positive theory // JournalSacerdote G. S. 1973, “Almost all free products of groups have the same positive theory”,Algebra. 1973. Vol. 27, № 3. P. 475-485.Journal Algebra, vol. 27, no. 3, pp. 475-485.Перязев Н. А. Позитивная неотличимость алгебраических систем и полнота позитивныхPeryazev N. A. 1985, “Positive indistinguishability of algebraic systems and completeness ofтеорий // Матем. заметки. 1985. Т. 38, № 2. С. 208-212.positive theories”, Mathem. notes, vol. 38, no. 2, pp. 208-212.Перязев Н. А. Позитивные теории свободных моноидов // Алгебра и логика. 1993. Т. 32,Peryazev N. A. 1993, “Positive theories of free monoids”, Algebra and logic, vol. 32, no. 2,№ 2. С. 148- 159.pp. 148-159.Ремеслеников В. Н. ∃-свободные группы // Сиб. матем. журнал. 1989. Т. 30, № 6. С. 193-Remeslenikov V. N. 1989, “∃-free groups”, Sib. mate. magazine, vol. 30, no. 6. pp. 193-197.Makanin G. S. 1984, “Solvability of universal and positive free theories groups”, Isv. USSRMakanin G. S. 1984, “Solvability of universal and positive free theories groups”, Isv. USSRМаканин Г. С. Разрешимость универсальной и позитивной теорий свободной группы //ACADEMY OF SCIENCES. Matem series, no. 2, pp. 35-749.Изв. АН СССР. Серия матем. 1984. № 2. С. 35-749.Matiyasevich Yu. V. 1970, “Diophancy of enumerated sets”, Dokl. USSR ACADEMY OFМатиясевич Ю.В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970.SCIENCES, vol. 130, no. 3. pp. 495-498.Т. 130, № 3. С. 495-498.Maltsev A. I. 1960, “About one correspondence between rings and groups”, Mathem. Sat.,Мальцев А. И. Об одном соответствии между кольцами и группами // Матем. сб. 1960.vol. 50, no. 2. pp. 257-266.Т. 50, № 2. С. 257-266.Borisov V. V., 1969, “Simple examples of groups with an unsolvable identity problem” //Борисов В. В. Простые примеры групп с неразрешимой проблемой тождества // Матем.Mathem. notes. 1969. Vol. 6, issue 5. pp. 521-532.заметки. 1969. Т. 6, вып. 5. С. 521-532.заметки. 1969. Т. 6, вып. 5. С. 521-532.

The authors declare that there are no conflicts of interest present.