Групповое Исчисление

ассоциативное исчисление, в к-ром эффективным образом выполнено естественное групповое требование существования обратной операции. Именно, ассоциативное исчисление наз. Г. И. (см. [1], с. 341), если для него может быть построен инвертирующий алгоритм, т. Е. Такой алгоритм , что для всякого слова Рв алфавите Аисчисления выполняются следующие условия. 1) определено и также является словом в А. 2) слова и эквивалентны в пустому слову (алгоритм здесь следует понимать в к.-л. Точном смысле слова, напр, как нормальный алгорифм). Наиболее употребительными являются Г. И. Специального типа (так наз. Инверсивные исчисления, см. [2]), у к-рых существование инвертирующего алгоритма обеспечивается надлежащим подбором их алфавитов и списков соотношений.

Алфавит инверсивного исчисления имеет четную длину, для каждой его буквы явно указывается обратная ей буква , а в список соотношений включается полный набор так наз. Тривиальных соотношений, т. Е. Соотношений, правые части к-рых суть пустые слова, а левые имеют вид . Роль Г. И. Определяется тем, что они являются представлениями конечно определенных групп. Г. И. , как и всякое ассоциативное исчисление, стандартным образом (см. Ассоциативное исчисление).порождает конечно определенную ассоциативную систему , к-рая вследствие наличия у инвертирующего алгоритма оказывается группой. Алгоритмическая проблема распознавания эквивалентности слов в Г. И. представляет собой формулированную в терминах Г. И. Проблему тождества для конечно определенной группы Это - первая из числа фундаментальных проблем разрешимости, сформулированных в 1911 М.

Деном [3] для конечно определенных групп. Рядом авторов было найдено положительное решение этой проблемы для групп, определяемых частными типами Г. И. В частности, оно было получено для групп, определяемых инверсивными исчислениями с одним нетривиальным соотношением (см. [4]). В 1952 П. С. Новиков (см. [5], а также [6]) впервые построил пример конечно определенной группы с неразрешимой проблемой тождества, т. Е. Группы, порожденной таким Г. И., для к-рого невозможен никакой алгоритм в уточненном смысле слова (напр., Тьюринга машина или нормальный алгорифм), решающий проблему эквивалентности слов в этом Г. И. Этот пример дает отрицательное решение проблемы тождества для конкретной конечно определенной группы с учетом современного уточнения этой проблемы, даваемого теорией алгоритмов (см.

Чёрча тезис). Впоследствии были приведены др. Примеры таких Г. И. (см., напр., [7], [8]). Упомянутый пример П. С. Новикова дает отрицательное решение и второй фундаментальной проблемы Дэна - проблемы распознавания пар слов, сопряженных в данном Г. И. Позднее П. С. Новиков [9] дал более простое и независимое от указанного примера отрицательное решение проблемы сопряженности. Большой интерес с алгебраич. Точки зрения представляет изучение тех свойств Г. И., к-рые оказываются инвариантными относительно изоморфизмов Г. И.,- это свойства абстрактных конечно определенных групп. В 1955 С. И. Адян [10]-[12] получил весьма общий результат, аналогичный результату А. А. Маркова для ассоциативных исчислений, давший отрицательное решение практически всех известных в то время алго-ритмич.

Проблем, связанных с основными классификациями Г. И. В частности, им было получено отрицательное решение третьей проблемы Дена - проблемы изоморфии любой фиксированной конечно определенной группе. Впоследствии аналогичные результаты получил М. Рабин [13]. Неразрешимость упомянутых алгоритмич. Проблем, касающихся Г. И., повлекла за собой отрицательное решение ряда алгоритмич. Проблем топологии. проблема гомотопии путей. Опираясь на результаты С. И. Адяна, А. А. Марков получил в 1958 отрицательное решение проблемы гомеоморфин (см. [14]). Лит.:[1] Марков А. А., Теория алгорифмов, М., 1954. [2] его же, "Изв. АН СССР. Сер. Матем.", 1963, т. 27, №4, с. 907-36. [3] Dehn M., "Math. Ann.", 1911, Bd 71, S. 116. [4] Magnus W., "J. Reine und angew. Math.", 1931, Brt 163, № 2, S.

141-65. [5] Новиков П. С., "Докл. АН СССР", 1952, т. 85, с. 709-12. [6] его же, Об алгоритмической неразрешимости проблемы тождества слов в теории групп, М., 1955. [7] Воone W. W., "Indagat. Math.", 1954, v. 16, p. 231, 492. 1955, v. 17, p. 252-56. 1957, v. 19, p. 22-7, 227-32. [8] Вrill on J. L., "Proc. London Math. Soc.", 3 ser., 1958, v. 8, № 32, p. 493-506. [9] Новиков П. С., "Изв. АН СССР. Сер. Матем.", 1954, т. 18, № 6, с. 485-524. [10] Адян С. И., "Докл. АН СССР", 1955, т. 103, с. 533-35. [11] его же, там же, 1957, т. 117, № 1, с. 9-12. [12] его же, "Тр. Моск. Матем. Об-ва", 1957, т. 6, с. 231-98. [13] Rabin M. О., "Ann. Math.", 1958, v. 67, p. 172-94. [14] Марков А. А., "Докл. АН СССР", 1958, т. 121, №2, с. 218-20. Н.