Проверка группы на конечность.

[Сомик]

Пусть группа $G$ задана конечным множеством порождающих элементов $A$ и конечным множеством определяющих соотношений $R$, т.е. задано конечное копредставление $<A|R>$. Меня интересует вопрос, как можно по копредставлению $<A|R>$ проверить конечность группы $G$. Можно ли это сделать алгоритмически? Если нет, то существуют ли какие-нибудь алгоритмически проверяемые достаточные условия того, что группа $G$ конечна (бесконечна).
Интересует литература или статьи на этот счёт.

Аналогичный вопрос интересует и про полугруппы.

[maxal]

Посмотрите, что умеет на эту тему GAP. Если такой алгоритм существует, то он скорее всего реализован в GAP - там же можно найти и ссылки на литературу.

[вздымщик Цыпа]

Сомик в сообщении #156879 писал(а):

Можно ли это сделать алгоритмически?

Нет. В общем случае такого алгоритма не существует.

Сомик в сообщении #156879 писал(а):

Если нет, то существуют ли какие-нибудь алгоритмически проверяемые достаточные условия того, что группа $G$ конечна (бесконечна).

Скорее всего, тоже нет.

Конечность — это марковское свойство. Т.е. свойство, которым обладает хотя бы одна группа и которым не обладает ни одна группа, содержащая некоторую фиксированную (для каждого свойства свою) группу в качестве подгруппы. Марковские свойства алгоритмически нераспознаваемы. К ним кроме конечности относятся коммутативность, единичность, разрешимость. См. теорему Адяна—Рабина.

[Сомик]

maxal
вздымщик Цыпа

Спасибо за ответы.