Введение

Проблема теории конечных групп В математике, особенно в области абстрактной алгебры, известной как комбинаторная теория групп, проблема слов для конечно порождённой группы — это алгоритмическая задача определения того, представляют ли два слова в генераторах один и тот же элемент. Проблема слов является хорошо известным примером неразрешимой задачи. Например, даны две биекции и на интервале , такие, что известно, можно ли доказать, что композиции и могут порождать только конечное число других биекций на без дополнительной информации о и ? Функции и называются генераторами, а множество всех конечных композиций и является группой, порождённой ими. В этом случае генераторы порождают конечную группу порядка 6, изоморфную группе симметрий равностороннего треугольника, , поэтому равенство двух произвольных конечных композиций можно определить. Более точно, если является конечным множеством генераторов для , то проблема слов — это задача о принадлежности к формальному языку всех слов в и формальному множеству обратных элементов, отображающихся в единичный элемент при естественном отображении из свободного моноида с инволюцией на в группу . Если является другим конечным порождающим множеством для , то проблема слов над порождающим множеством эквивалентна проблеме слов над порождающим множеством . Таким образом, можно однозначно говорить о разрешимости проблемы слов для конечно порождённой группы. Связанная, но отличная единая проблема слов для класса рекурсивно представленных групп — это алгоритмическая задача определения, задано в качестве входных данных представление для группы в классе и два слова в генераторах , представляют ли слова один и тот же элемент . Некоторые авторы требуют, чтобы класс был определяем рекурсивно перечислимым множеством представлений.

История

На протяжении всей истории изучения групп вычисления в группах выполнялись с использованием различных нормальных форм. Эти формы обычно неявно решают проблему слов для рассматриваемых групп. В 1911 году Макс Ден предложил, что проблема слов является важной областью исследования сама по себе, наряду с проблемой сопряжённости и проблемой изоморфизма групп. В 1912 году он разработал алгоритм, решающий как проблему слов, так и проблему сопряжённости для фундаментальных групп замкнутых ориентируемых двумерных многообразий рода, большего или равного 2. Последующие исследователи значительно расширили алгоритм Дена и применили его к широкому спектру задач принятия решений в теории групп. В 1955 году Пётр Новиков показал, что существует конечно представленная группа, для которой проблема слов неразрешима. Непосредственно из этого следует, что и единая проблема слов также неразрешима. В 1958 году Уильям Бун получил другое доказательство. Проблема слов стала одним из первых примеров неразрешимой задачи, обнаруженной не в математической логике или теории алгоритмов, а в одной из центральных областей классической математики – алгебре. Вследствие своей неразрешимости, несколько других задач в комбинаторной теории групп также оказались неразрешимыми. Важно понимать, что проблема слов фактически разрешима для многих групп. Например, полициклические группы имеют разрешимые проблемы слов, поскольку нормальная форма произвольного слова в полициклической презентации легко вычисляется; другие алгоритмы для групп также могут решать проблему слов в подходящих условиях, например, алгоритм Тодда — Кокстера и алгоритм завершения Кнута — Бендикса. С другой стороны, тот факт, что конкретный алгоритм не решает проблему слов для конкретной группы, не означает, что у этой группы неразрешимая проблема слов. Например, алгоритм Дена не решает проблему слов для фундаментальной группы тора. Однако эта группа является прямым произведением двух бесконечных циклических групп и, следовательно, имеет разрешимую проблему слов.

Более конкретное описание

В более конкретных терминах, единая проблема о словах может быть выражена как вопрос о переписывании для литеральных строк. Для заданной презентации группы будет указано определенное количество генераторов для . Нам нужно ввести одну букву для и другую (для удобства) для элемента группы, представленного этими буквами (вдвое больше, чем генераторов) – это будет алфавит для нашей задачи. Затем каждый элемент в будет представлен каким-то образом произведением символов из , некоторой длины, умноженных друг на друга. Строка длины 0 (пустая строка) представляет собой единичный элемент . Суть всей проблемы заключается в том, чтобы уметь распознавать все способы, которыми может быть представлен, учитывая некоторые соотношения. Эффект соотношений в заключается в том, что различные такие строки представляют один и тот же элемент . Фактически, соотношения предоставляют список строк, которые можно либо вставлять, где мы хотим, либо вычеркивать, когда мы их видим, не изменяя "значение", то есть элемент группы, который является результатом умножения. Для простого примера рассмотрим группу, заданную презентацией . Обозначая обратным к , у нас есть возможные строки, объединяющие любое количество символов и . Когда мы видим , или , или , мы можем вычеркнуть их. Мы также должны помнить о вычеркивании ; это означает, что поскольку куб является единичным элементом , то и куб обратного к является единичным элементом. В этих условиях проблема о словах становится простой. Сначала сократим строки до пустой строки, , , или . Затем обратите внимание, что мы также можем умножить на , поэтому мы можем преобразовать в и в . Результатом является то, что проблема о словах, здесь для циклической группы порядка три, разрешима. Однако это не типичный случай. В данном примере у нас есть каноническая форма, которая уменьшает любую строку до длины не более трех, монотонно уменьшая длину. В общем случае нельзя получить каноническую форму для элементов путем последовательного вычеркивания. Возможно, придется использовать соотношения для многократного расширения строки, чтобы в конечном итоге найти вычеркивание, которое значительно уменьшит длину. В худшем случае отношение между строками, указывающее на их равенство в , является неразрешимой проблемой.