Проблема разрешимости позитивной теории произвольной группы алгоритмически неразрешима
https://doi.org/10.22405/2226-8383-2023-24-1-40-49
Аннотация
В статье доказано, что невозможно построить алгоритм, позволяющий по произвольному конечному заданию группы определить, разрешима ли ее позитивная теория. Указанное
групповое свойство не является марковским, поэтому к нему не применима фундаментальная теорема Адяна – Рабина.
Ключевые слова
позитивная формула,
позитивная теория группы,
позитивная теория класса групп,
алгоритмическая разрешимость,
алгоритмическая неразрешимость.
При поддержке: Работа выполнена при финансовой поддержке РФФИ (проект № 19 - 52 - 26006).
Об авторах
Валерий Георгиевич Дурнев
Ярославский государственный университет им. П. Г. Демидова
Россия
Россия
Алена Игоревна Зеткина
Ярославский государственный университет им. П. Г. Демидова; Воронежский государственный университет
Россия
Россия
Список литературы
1. Адян С. И. Алгоритмическая неразрешимость проблем распознавания некоторых свойств
2. групп // Докл. АН СССР. 1955. Т. 103, № 4. С. 533–535.
3. Адян С. И. Неразрешимость некоторых алгоритмических проблем теории групп // Труды
4. ММО. 1957. Т. 6. С. 231-298.
5. Rabin M. O. Recursive unsolvability of group theoretic problems // Ann. of Math. 1958. Vol. 67,
6. № 1. P. 172-194.
7. Collings D. J. On recognizing Hopf groups // Arh. Math. 1969. Vol. 20. P. 235-240.
8. Miller C. F. III. Decision problems for groups – servey and reflections // Math. Sci. Res. Inst.
9. Publ. 1992. Vol. 23. P. 1-59.
10. Miller C. F. III, Schupp P.E. Embeddings into Hopfian groups // Journal Algebra, 1971. Vol. 17.
11. P. 171-176.
12. Miller C. F. III. On group-theoretic decision problems and their classification // Ann. of Math.
13. Studies. 1971. Vol. 68. Princeton University Press.
14. Мерзляков Ю. И. Позитивные формулы на свободных группах. // Алгебра и логика. 1966.
15. Т. 5, вып. 4. С. 25-42.
16. Sacerdote G. S. Almost all free products of groups have the same positive theory // Journal
17. Algebra. 1973. Vol. 27, № 3. P. 475-485.
18. Перязев Н. А. Позитивная неотличимость алгебраических систем и полнота позитивных
19. теорий // Матем. заметки. 1985. Т. 38, № 2. С. 208-212.
20. Перязев Н. А. Позитивные теории свободных моноидов // Алгебра и логика. 1993. Т. 32,
21. № 2. С. 148- 159.
22. Ремеслеников В. Н. ∃-свободные группы // Сиб. матем. журнал. 1989. Т. 30, № 6. С. 193-
23.
24. Маканин Г. С. Разрешимость универсальной и позитивной теорий свободной группы //
25. Изв. АН СССР. Серия матем. 1984. № 2. С. 35-749.
26. Матиясевич Ю.В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970.
27. Т. 130, № 3. С. 495-498.
28. Мальцев А. И. Об одном соответствии между кольцами и группами // Матем. сб. 1960.
29. Т. 50, № 2. С. 257-266.
30. Борисов В. В. Простые примеры групп с неразрешимой проблемой тождества // Матем.
31. заметки. 1969. Т. 6, вып. 5. С. 521-532.
Рецензия
Для цитирования:
Дурнев В.Г., Зеткина А.И. Проблема разрешимости позитивной теории произвольной группы алгоритмически неразрешима. Чебышевский сборник. 2023;24(1):40-49. https://doi.org/10.22405/2226-8383-2023-24-1-40-49
For citation:
Durnev V.G., Zetkina A.I. The problem of solvability of a positive theory of an arbitrary group is algorithmically unsolvable. Chebyshevskii Sbornik. 2023;24(1):40-49. (In Russ.) https://doi.org/10.22405/2226-8383-2023-24-1-40-49
Просмотров:
310
Послать статью по эл. почте 