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

Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к Сделайте это понятным для неспециалистов, не снимая технических деталей. (Декабрь 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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

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

Грубо говоря, проблема слов в алгебре: задано множество E идентичностей ( эквациональная теория ), и два термины s и т, возможно ли преобразовать s в т используя личности в E в качестве переписывание правила в обе стороны ?.^[1] Правильное расширение проблема со словом известен как проблема объединения (он же задача решения уравненияВ то время как первый спрашивает, есть ли два термина находятся равны, последний спрашивает, есть ли у них экземпляры которые равны. В качестве распространенного примера: "${ Displaystyle 2 + 3 { stackrel {?} {=}} 8 + (- 3)}$"проблема со словом в целая группа ℤ,пока "${ Displaystyle 2 + х { stackrel {?} {=}} 8 + (- х)}$"является проблемой объединения в той же группе; поскольку первые члены оказываются равными в ℤ, вторая задача имеет замена ${ Displaystyle {х 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 (а cdot b)}$ и ${ Displaystyle б cdot (1 cdot а)}$ имеет нормальную форму ${ 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 (х cdot y) cdot z}$	${ Displaystyle = х CDOT (у CDOT г)}$

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

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

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

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

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