Алгоритмические проблемы для групп и полугрупп

В статье дается подробный обзор результатов по основным алгоритмическим проблемам теории групп и полугрупп: проблемам равенства, изоморфизма, распознавания свойств и другим алгоритмическим вопросам, связанным с этими проблемами. Известные теоремы Маркова–Поста, П. С. Новикова, Адяна–Рабина, Хигмана, Магнуса, Линдона изложены с полными доказательствами. Как правило, приводимые в обзоре доказательства этих теорем существенно проще тех, которые давались авторами теорем в их оригинальных работах. В началe статьи для полноты приводится доказательство результата о неразрешимости проблемы остановки для машин Тьюринга, на котором основывается неразрешимость проблемы равенства для полугрупп. Особое внимание уделено также простейшим примерам полугрупп с неразрешимой проблемой равенства. Подробно изложено доказательство весьма примечательного результата Р. Линдона о разрешимости проблемы равенства в классе групп, задаваемых системой определяющих соотношений с условием, что максимальное взаимное наложение определяющих слов строго меньше $1/5$ длины самих этих слов, в то время как при замене в этом условии строгого неравенства на нестрогое уже возникает возможность неразрешимости. Изложено также доказательство аналогичного результата для конечно определенных полугрупп, где соответствующая точная граница равна $1/2$.
Библиография: 110 названий.