Проблема со словом (математика) - Word problem (mathematics)

Эта статья об алгоритмических задачах слов в математике и информатике. Для использования в других целях см. Проблема со словом.

В математика и Информатика, а проблема со словом для множества S относительно системы конечных кодировок его элементов является алгоритмическая проблема решения представляют ли два заданных представителя один и тот же элемент множества. Проблема обычно встречается в абстрактная алгебра, где дано представление алгебраической структуры с помощью генераторы и родственники, проблема состоит в том, чтобы определить, представляют ли два выражения один и тот же элемент; прототипическим примером является проблема слов для групп. Менее формально проблема слов в алгебре такова: задан набор тождеств E, и два выражения Икс и у, возможно ли преобразовать Икс в у используя личности в E в качестве переписывание правила в обе стороны? Хотя ответ на этот вопрос может показаться несложным, замечательные (и глубокий ) результат, который оказывается во многих важных случаях, заключается в том, что проблема неразрешима.

Многие, если не все, неразрешимые математические задачи можно представить в виде словесных задач; увидеть список неразрешимых проблем для многих примеров.

Предпосылки и мотивация

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

По разным причинам не всегда возможно или желательно использовать систему уникальный encodings, то есть такой, в котором каждый элемент имеет единственную кодировку. При использовании системы кодирования без уникальности естественно возникает вопрос, существует ли алгоритм, который, заданные в качестве входных двух кодировок, решает, представляют ли они один и тот же элемент. Такой алгоритм называется решение проблемы со словом для системы кодирования.

Проблема слов в комбинаторном исчислении

Основная статья: Комбинаторная логика § Неразрешимость комбинаторного исчисления

Простейший пример неразрешимой проблемы со словами возникает в комбинаторная логика: когда две строки комбинаторов эквивалентны? Поскольку комбинаторы кодируют все возможные Машины Тьюринга, а эквивалентность двух машин Тьюринга неразрешима, отсюда следует, что эквивалентность двух цепочек комбинаторов неразрешима.

Точно так же, по сути, та же проблема в (нетипизированном) лямбда-исчисление: учитывая два различных лямбда-выражения, нет алгоритма, который мог бы различить, эквивалентны они или нет; эквивалентность неразрешима. Для нескольких типизированных вариантов лямбда-исчисления эквивалентность разрешима путем сравнения нормальных форм.

Проблема слова в универсальной алгебре

В алгебра, часто изучаются бесконечные алгебры, которые порождаются (при финишный операции алгебры) конечным числом элементов. В этом случае элементы алгебры имеют естественную систему конечного кодирования как выражения в терминах генераторов и операций. Таким образом, проблема слов здесь состоит в том, чтобы определить, учитывая два таких выражения, представляют ли они один и тот же элемент алгебры.

Грубо говоря, проблема слов в алгебре: задано множество E идентичностей ( эквациональная теория ), и два термины s и т, возможно ли преобразовать s в т используя личности в E в качестве переписывание правила в обе стороны ?.^[1] Правильное расширение проблема со словом известен как проблема объединения (он же задача решения уравненияВ то время как первый спрашивает, есть ли два термина находятся равны, последний спрашивает, есть ли у них экземпляры которые равны. В качестве распространенного примера: "${\displaystyle 2+3{\stackrel {?}{=}}8+(-3)}$"проблема со словом в целая группа ℤ,пока "${\displaystyle 2+x{\stackrel {?}{=}}8+(-x)}$"является проблемой объединения в той же группе; поскольку первые члены оказываются равными в ℤ, вторая задача имеет замена ${\displaystyle \{x\mapsto 3\}}$ как решение.

Замены могут быть заказаны в частичный заказ, таким образом, объединение - это акт поиска присоединиться на решетка.^{[требуется разъяснение ]}В этом смысле проблема слов на решетке имеет решение, а именно, множество всех эквивалентных слов есть свободная решетка.^{[требуется разъяснение ]}

Один из наиболее глубоко изученных случаев проблемы слова находится в теории полугруппы и группы. Есть много групп, для которых слово проблема не является разрешимый, в том, что нет машины Тьюринга, которая могла бы определить эквивалентность двух произвольный слова за конечное время.

Слово проблема на основные условия не разрешима.^{[2][требуется разъяснение ]}

Слово проблема бесплатно Гейтинговые алгебры трудно.^[3] Единственные известные результаты заключаются в том, что свободная алгебра Гейтинга на одном образующем бесконечна, а свободная алгебра полная алгебра Гейтинга на одной образующей существует (и имеет на один элемент больше, чем свободная алгебра Гейтинга).

Пример: система переписывания терминов для решения проблемы слов в свободной группе.

Блазиус и Бюркерт ^[4]продемонстрировать Алгоритм Кнута – Бендикса на множестве аксиом для групп. Алгоритм дает сливаться и нётерский система перезаписи терминов который превращает каждый термин в уникальный нормальная форма.^[5] Правила перезаписи пронумерованы как непоследовательные, поскольку некоторые правила стали избыточными и были удалены во время работы алгоритма. Равенство двух членов следует из аксиом тогда и только тогда, когда оба термина преобразуются в буквально один и тот же терм нормальной формы. Например, условия

${\displaystyle ((a^{-1}\cdot a)\cdot (b\cdot b^{-1}))^{-1}{\stackrel {R2}{\rightsquigarrow }}(1\cdot (b\cdot b^{-1}))^{-1}{\stackrel {R13}{\rightsquigarrow }}(1\cdot 1)^{-1}{\stackrel {R1}{\rightsquigarrow }}1^{-1}{\stackrel {R8}{\rightsquigarrow }}1}$, и

${\displaystyle b\cdot ((a\cdot b)^{-1}\cdot a){\stackrel {R17}{\rightsquigarrow }}b\cdot ((b^{-1}\cdot a^{-1})\cdot a){\stackrel {R3}{\rightsquigarrow }}b\cdot (b^{-1}\cdot (a^{-1}\cdot a)){\stackrel {R2}{\rightsquigarrow }}b\cdot (b^{-1}\cdot 1){\stackrel {R11}{\rightsquigarrow }}b\cdot b^{-1}{\stackrel {R13}{\rightsquigarrow }}1}$

имеют ту же нормальную форму, а именно. ${\displaystyle 1}$; поэтому оба члена равны в каждой группе. В качестве другого примера, термин ${\displaystyle 1\cdot (a\cdot b)}$ и ${\displaystyle b\cdot (1\cdot a)}$ имеет нормальную форму ${\displaystyle a\cdot b}$ и ${\displaystyle b\cdot a}$, соответственно. Поскольку нормальные формы буквально различны, исходные термины не могут быть одинаковыми в каждой группе. На самом деле они обычно разные по неабелевы группы.

Групповые аксиомы, использованные при пополнении Кнута – Бендикса

A1	${\displaystyle 1\cdot x}$	${\displaystyle =x}$
A2	${\displaystyle x^{-1}\cdot x}$	${\displaystyle =1}$
A3	${\displaystyle (x\cdot y)\cdot z}$	${\displaystyle =x\cdot (y\cdot z)}$

Система переписывания терминов, полученная в результате завершения Кнута – Бендикса

R1	${\displaystyle 1\cdot x}$	${\displaystyle \rightsquigarrow x}$
R2	${\displaystyle x^{-1}\cdot x}$	${\displaystyle \rightsquigarrow 1}$
R3	${\displaystyle (x\cdot y)\cdot z}$	${\displaystyle \rightsquigarrow x\cdot (y\cdot z)}$
R4	${\displaystyle x^{-1}\cdot (x\cdot y)}$	${\displaystyle \rightsquigarrow y}$
R8	${\displaystyle 1^{-1}}$	${\displaystyle \rightsquigarrow 1}$
R11	${\displaystyle x\cdot 1}$	${\displaystyle \rightsquigarrow x}$
R12	${\displaystyle (x^{-1})^{-1}}$	${\displaystyle \rightsquigarrow x}$
R13	${\displaystyle x\cdot x^{-1}}$	${\displaystyle \rightsquigarrow 1}$
R14	${\displaystyle x\cdot (x^{-1}\cdot y)}$	${\displaystyle \rightsquigarrow y}$
R17	${\displaystyle (x\cdot y)^{-1}}$	${\displaystyle \rightsquigarrow y^{-1}\cdot x^{-1}}$

Смотрите также

• Манн дерево
• Задача со словом для групп
• Алгоритм завершения Кнута – Бендикса
• Объединение (информатика)

Рекомендации

1. Франц Баадер и Тобиас Нипков, Перезапись терминов и все такое, Cambridge University Press, 1998, стр. 5
2. Юрий Матиясевич, (1967) "Простые примеры неразрешимых ассоциативных исчислений", Советская математика - Доклады 8(2) стр. 555–557.
3. Питер Т. Джонстон, Каменные Пространства(1982) Издательство Кембриджского университета, Кембридж, ISBN  0-521-23893-5. (См. Главу 1, параграф 4.11)
4. К. Х. Блейсиус и Х.-Ж. Bürckert, ed. (1992). Deduktionsssysteme. Ольденбург. п. 291.; здесь: с.126, 134
5. Применять правила в любом порядке к сроку как можно дольше; результат не зависит от заказа; это нормальная форма термина.