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

ассоциативное исчисление, в к-ром эффективным образом выполнено естественное групповое требование существования обратной операции. Именно, ассоциативное исчисление наз. Г. и. (см. [1], с. 341), если для него может быть построен инвертирующий алгоритм, т. е. такой алгоритм [img: http://localhost:8080/file/010432-87.jpg], что для всякого слова Рв алфавите Аисчисления [img: http://localhost:8080/file/010432-88.jpg] выполняются следующие условия: 1) [img: http://localhost:8080/file/010432-89.jpg] определено и также является словом в А; 2) слова [img: http://localhost:8080/file/010432-90.jpg] и [img: http://localhost:8080/file/010432-91.jpg] эквивалентны в [img: http://localhost:8080/file/010432-92.jpg] пустому слову (алгоритм здесь следует понимать в к.-л. точном смысле слова, напр, как нормальный алгорифм). Наиболее употребительными являются Г. и. специального типа (так наз. инверсивные исчисления, см. [2]), у к-рых существование инвертирующего алгоритма обеспечивается надлежащим подбором их алфавитов и списков соотношений: алфавит инверсивного исчисления имеет четную длину, для каждой его буквы [img: http://localhost:8080/file/010432-93.jpg] явно указывается обратная ей буква [img: http://localhost:8080/file/010432-94.jpg], а в список соотношений включается полный набор так наз. тривиальных соотношений, т. е. соотношений, правые части к-рых суть пустые слова, а левые имеют вид [img: http://localhost:8080/file/010432-95.jpg]. Роль Г. и. определяется тем, что они являются представлениями конечно определенных групп. Г. и. [img: http://localhost:8080/file/010432-96.jpg], как и всякое ассоциативное исчисление, стандартным образом (см. Ассоциативное исчисление).порождает конечно определенную ассоциативную систему [img: http://localhost:8080/file/010432-97.jpg], к-рая вследствие наличия у [img: http://localhost:8080/file/010432-98.jpg] инвертирующего алгоритма оказывается группой. Алгоритмическая проблема распознавания эквивалентности слов в Г. и. [img: http://localhost:8080/file/010432-99.jpg] представляет собой формулированную в терминах Г. и. проблему тождества для конечно определенной группы [img: http://localhost:8080/file/010432-100.jpg] Это - первая из числа фундаментальных проблем разрешимости, сформулированных в 1911 М. Деном [3] для конечно определенных групп. Рядом авторов было найдено положительное решение этой проблемы для групп, определяемых частными типами Г. и. В частности, оно было получено для групп, определяемых инверсивными исчислениями с одним нетривиальным соотношением (см. [4]). В 1952 П. С. Новиков (см. [5], а также [6]) впервые построил пример конечно определенной группы с неразрешимой проблемой тождества, т. е. группы, порожденной таким Г. и., для к-рого невозможен никакой алгоритм в уточненном смысле слова (напр., Тьюринга машина или нормальный алгорифм), решающий проблему эквивалентности слов в этом Г. и. Этот пример дает отрицательное решение проблемы тождества для конкретной конечно определенной группы с учетом современного уточнения этой проблемы, даваемого теорией алгоритмов (см. Чёрча тезис). Впоследствии были приведены др. примеры таких Г. и. (см., напр., [7], [8]). Упомянутый пример П. С. Новикова дает отрицательное решение и второй фундаментальной проблемы Дэна - проблемы распознавания пар слов, сопряженных в данном Г. и. Позднее П. С. Новиков [9] дал более простое и независимое от указанного примера отрицательное решение проблемы сопряженности. Большой интерес с алгебраич. точки зрения представляет изучение тех свойств Г. и., к-рые оказываются инвариантными относительно изоморфизмов Г. и.,- это свойства абстрактных конечно определенных групп. В 1955 С. И. Адян [10]-[12] получил весьма общий результат, аналогичный результату А. А. Маркова для ассоциативных исчислений, давший отрицательное решение практически всех известных в то время алго-ритмич. проблем, связанных с основными классификациями Г. и. В частности, им было получено отрицательное решение третьей проблемы Дена - проблемы изоморфии любой фиксированной конечно определенной группе. Впоследствии аналогичные результаты получил М. Рабин [13]. Неразрешимость упомянутых алгоритмич. проблем, касающихся Г. и., повлекла за собой отрицательное решение ряда алгоритмич. проблем топологии. проблема гомотопии путей. Опираясь на результаты С. И. Адяна, А. А. Марков получил в 1958 отрицательное решение проблемы гомеоморфин (см. [14]).