2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение09.11.2008, 02:06 
Аватара пользователя
Посмотрите, что умеет на эту тему GAP. Если такой алгоритм существует, то он скорее всего реализован в GAP - там же можно найти и ссылки на литературу.

 
 
 
 
Сообщение09.11.2008, 02:26 
Сомик в сообщении #156879 писал(а):
Можно ли это сделать алгоритмически?
Нет. В общем случае такого алгоритма не существует.
Сомик в сообщении #156879 писал(а):
Если нет, то существуют ли какие-нибудь алгоритмически проверяемые достаточные условия того, что группа $G$ конечна (бесконечна).
Скорее всего, тоже нет.

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

 
 
 
 
Сообщение10.11.2008, 13:36 
Аватара пользователя
maxal
вздымщик Цыпа

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group