Cтраница 1
Проблема слов представляет собой далеко идущее обобщение поисков Тезея, Если поиски Тезея могут происходить в произвольном, но к о н е ч н о м лабиринте, то проблема слов является в определенном смысле проблемой поиска в бесконечном лабиринте. [1]
Решение проблемы слов позволяет без труда получить некоторую информацию о подгруппах свободных групп. [2]
Однако если вернуться к неограниченной проблеме слов, то там положение существенно иное. Поскольку длина дедуктивной цепочки, ведущей от R к Т ( если такая существует), может оказаться сколь угодно большой, то, вообще говоря, неизвестно, когда следует считать законченным процесс перебора. Пусть, например, мы уже продолжили процесс перебора до К) 20 100 000 000 000 000 000 000 и уже располагаем списком всех слов, которые можно получить из R при помощи многократных применений подстановок, общее число которых не превосходит 1020, и пусть в этом списке слова Т не оказалось. Разумеется, нет, ибо не исключена возможность, что R к Т эквивалентны, но минимальная дедуктивная цепочка, соединяющая их, еще длиннее. [3]
Тогда в группе G разрешима проблема слов. [4]
Может создаться впечатление, что проблема слов представляет собой искусственно надуманную головоломку, и, следовательно, нахождение такого алгоритма не представляет собой особого практического или теоретического интереса. На самом же деле это далеко не так; можно показать, что эта проблема является весьма естественной и имеет большое теоретическое и практическое значение, вполне оправдывающее усилия, направленные на построение соответствующего алгоритма. [5]
Тот же метод индукции дает решение проблемы слов для групп с одним соотношением. [6]
В частности, для группы G разрешима проблема слов. [7]
Установление единственности нормальной формы приводит к решению проблемы слов, при условии, что эта нормальная форма может быть эффективно вычислена. Для G Gi G2: А А % у основной задачей при вычислении нормальной формы является задач. [8]
Конечно представленная группа G с контекстно свдОодной проблемой слов имеет более одного конца. [9]
Для любой группы с одним определяющим соотношением разрешима проблема слов. [10]
Проблема сопряженности для группы кос оказывается намного более сложной, чем проблема слов. Поскольку не известно достаточно легко описываемого решения, мы не будем комментировать этот результат подробнее. Проблема сопряженности эквивалентна проблеме классификации замкнутых п-кос ( см. 5.3.11), что может быть использовано как первый шаг к классификации произвольных зацеплений. Вторым шагом является процедура стабилизации, то есть добавления к замкнутой косе новой тривиальной нити и выяснения, какие замкнутые / г-косы становятся при этом эквивалентными ( п 1) - косами. Все это показывает важность решения проблемы сопряженности для групп кос. [11]
В течение многих лет математики пытались найти пример конечно-определенной) группы, для которой проблема слов была бы неразрешима. В конце концов Новиков в 1955 году и Бун в 1957 году показали, что такие группы существуют. Доказательства теоремы Новикова - Буна выходят за рамки настоящего обзора. [12]
Важность этой группы в топологии несомненна, а после решения Дэном для этой группы проблем слов и сопряженности существенно повзрослела и комбинаторная теория групп. Именно Дэн предположил, что для произвольных групп с одним определяющим соотношением должны выполняться утверждения, установленные им для групп поверхностей. [13]
Для того чтобы лучше уяснить специфику тех трудностей, которые здесь возникают, рассмотрим предварительно ограниченную проблему слов, которая заключается в следующем. [14]
Заметим, что для пустого множества Ц это есть требование того, чтобы была разрешима проблема слов. [15]