Введение
Проблема решения, касающаяся эквивалентности выражений
В вычислительной математике проблема слов — это задача определения, эквивалентны ли два заданных выражения относительно некоторого набора тождеств переписывания. Типичным примером является проблема слов для групп, но существует множество других случаев. Важный результат теории вычислимости заключается в том, что ответ на этот вопрос во многих важных случаях является неразрешимым. Например, можно определить, что является нормальной формой для , , и , и разработать систему преобразований для приведения этих выражений к этой форме, тем самым доказывая, что все эквивалентные выражения будут преобразованы в одну и ту же нормальную форму. Однако не все решения проблемы слов используют теорему о нормальной форме — существуют алгебраические свойства, которые косвенно подразумевают существование алгоритма.
Проблема слов для полу-Thue систем
Проблема доступности для систем переписывания строк (полу-Тью системы или полугруппы) может быть сформулирована следующим образом: задана полу-Тью система и две строки (слова) , можно ли преобразовать строку в строку , применяя правила из ? Следует отметить, что переписывание в данном случае одностороннее. Проблема равенства слов – это проблема доступности для симметричных отношений переписывания, то есть систем Тью. Проблемы доступности и равенства слов неразрешимы, то есть не существует общего алгоритма для их решения. Это справедливо даже в случае ограничения систем конечными представлениями, то есть конечным множеством символов и конечным множеством соотношений на этих символах.
Проблема слов для групп
При заданном представлении группы G, словесная проблема — это алгоритмическая задача определения, представляют ли два заданных слова в S один и тот же элемент G. Словесная проблема является одной из трех алгоритмических задач для групп, предложенных Максом Деном в 1911 году. Пётр Новиков в 1955 году показал, что существует конечно представленная группа G, для которой словесная проблема неразрешима.
Проблема слова в комбинаторном исчислении и ламбда-расчете
Одним из самых ранних доказательств неразрешимости словесной задачи стала комбинаторная логика: при каких условиях две строки комбинаторов эквивалентны? Поскольку комбинаторы кодируют все возможные машины Тьюринга, а эквивалентность двух машин Тьюринга неразрешима, следует, что эквивалентность двух строк комбинаторов также неразрешима. Алонсо Черч отметил это в 1936 году. Подобная проблема возникает и в (нетипизированном) лямбда-исчислении: для любых двух различных лямбда-выражений не существует алгоритма, позволяющего определить, эквивалентны ли они; эквивалентность неразрешима. Для ряда типизированных вариантов лямбда-исчисления эквивалентность можно определить, сравнивая их нормальные формы.
Проблема слов для абстрактных систем переписывания
Слово задачи для абстрактной системы переписывания (ARS) формулируется кратко: даны объекты x и y, эквивалентны ли они относительно отношения ? В общем случае, задача о равенстве для АРС неразрешима. Однако, существует вычислимое решение задачи о равенстве в частном случае, когда каждый объект сводится к единственной нормальной форме за конечное число шагов (то есть система является сходящейся): два объекта эквивалентны относительно отношения тогда и только тогда, когда они сводятся к одной и той же нормальной форме. Алгоритм завершения Кнута — Бендикса можно использовать для преобразования набора уравнений в сходящуюся систему переписывания термов.
Слово "проблема" в универсальной алгебре
В универсальной алгебре изучаются алгебраические структуры, состоящие из генерирующего множества A, набора операций над A конечной арности и конечного множества тождеств, которым эти операции должны удовлетворять. Словозадача для алгебры заключается в том, чтобы определить, представляют ли два выражения (слова), содержащие генераторы и операции, один и тот же элемент алгебры по модулю тождеств. Словозадачи для групп и полугрупп могут быть сформулированы как словозадачи для алгебр. Единственные известные результаты заключаются в том, что свободная алгебра Хейтинга с одним генератором бесконечна, и что свободная полная алгебра Хейтинга с одним генератором существует (и содержит на один элемент больше, чем свободная алгебра Хейтинга).