Словесная задача (математика)

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

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

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

В компьютерной алгебре часто требуется закодировать математические выражения с помощью дерева выражений. Но часто существует несколько эквивалентных деревьев выражений. Естественно возникает вопрос, существует ли алгоритм, который, учитывая два входных выражения, решает, представляют ли они один и тот же элемент. Такой алгоритм называется решением проблемы слова . Например, представьте, что $x,y,z$ являются символами, представляющими действительные числа , тогда подходящее решение проблемы со словами будет, учитывая входные данные $(x\cdot y)/z\mathrel {\overset {?}{=}} (x/z)\cdot y$, произвести вывод EQUALи аналогичным образом производят NOT_EQUAL от $(x\cdot y)/z\mathrel {\overset {?}{=}} (x/x)\cdot y$.

Наиболее прямое решение проблемы со словами принимает форму теоремы и алгоритма нормальной формы, который отображает каждый элемент в классе эквивалентности выражений в одну кодировку, известную как нормальная форма . Затем проблема со словами решается путем сравнения этих нормальных форм с помощью синтаксическое равенство . Например, можно решить, что $x\cdot y\cdot z^{-1}$ это нормальная форма $(x\cdot y)/z$, $(x/z)\cdot y$, и $(y/z)\cdot x$и разработайте систему преобразований для перезаписи этих выражений в эту форму, при этом доказывая, что все эквивалентные выражения будут переписаны в одну и ту же нормальную форму. Но не все решения проблемы слов используют теорему о нормальной форме — существуют алгебраические свойства, которые косвенно подразумевают существование алгоритма.

В то время как проблема слов спрашивает, равны ли два термина, содержащих константы , правильное расширение проблемы слов, известное как проблема объединения, спрашивает, равны ли два термина, содержащие константы. $t_{1},t_{2}$ содержащие переменные имеют экземпляры , которые равны, или, другими словами, уравнение $t_{1}=t_{2}$ имеет какие-либо решения. В качестве общего примера, $2+3\mathrel {\overset {?}{=}} 8+(-3)$ это задача на слова в целочисленной группе $\mathbb {Z}$,пока $2+x\mathrel {\overset {?}{=}} 8+(-x)$ – проблема объединения в одной группе; поскольку первые члены оказываются равными по $\mathbb {Z}$, последняя задача имеет замену $\{x\mapsto 3\}$ как решение.

История

Один из наиболее глубоко изученных случаев проблемы слова находится в теории полугрупп и групп . Хронология статей, имеющих отношение к теореме Новикова-Буна , следующая:

• 1910 ( 1910 ) : Аксель Туэ ставит общую проблему переписывания терминов в древовидных структурах. Он утверждает: «Решение этой проблемы в самом общем случае может быть связано, пожалуй, с непреодолимыми трудностями».
• 1911 ( 1911 ) : Макс Ден ставит проблему слов для конечно определенных групп .
• 1912 ( 1912 ) : Ден представляет алгоритм Дена и доказывает, что он решает проблему слов для фундаментальных групп замкнутых ориентируемых двумерных многообразий рода, большего или равного 2. Последующие авторы значительно расширили его на широкий круг теоретико-групповых задач принятия решений.
• 1914 ( 1914 ) : Аксель Туэ ставит проблему слов для конечно определенных полугрупп.
• 1930 ( 1930 ) – 1938 ( 1938 ) : Возникает тезис Чёрча-Тьюринга , определяющий формальные понятия вычислимости и неразрешимости.
• 1947 ( 1947 ) : Эмиль Пост и Андрей Марков-младший независимо друг от друга строят конечно определенные полугруппы с неразрешимой проблемой слов. Конструкция Поста построена на машинах Тьюринга , а конструкция Маркова использует обычные системы Поста.
• 1950 ( 1950 ) : Алан Тьюринг показывает, что проблема слов для полугрупп сокращения неразрешима. способствуя строительству Поста. Доказательство трудно понять, но оно знаменует собой поворотный момент в проблеме слов для групп.
• 1955 ( 1955 ) : Петр Новиков дает первое опубликованное доказательство неразрешимости проблемы слов для групп, используя результат Тьюринга о сокращении полугруппы. Доказательство содержит «Основную лемму», эквивалентную лемме Бриттона .
• 1954 ( 1954 ) – 1957 ( 1957 ) : Уильям Бун независимо показывает, что проблема слов для групп неразрешима, используя конструкцию полугруппы Поста.
• 1957 ( 1957 ) – 1958 ( 1958 ) : Джон Бриттон дает еще одно доказательство неразрешимости проблемы слов для групп, основанное на результате Тьюринга о сокращении полугрупп и некоторых более ранних работах Бриттона. Появляется ранняя версия леммы Бриттона.
• 1958 ( 1958 ) — 1959 ( 1959 ) : Бун публикует упрощенную версию своей конструкции.
• 1961 ( 1961 ) : Грэм Хигман характеризует подгруппы конечно представленных групп с помощью теоремы вложения Хигмана , неожиданным образом соединив теорию рекурсии с теорией групп и дав совершенно иное доказательство неразрешимости проблемы слов.
• 1961 ( 1961 ) – 1963 ( 1963 ) : Бриттон представляет значительно упрощенную версию доказательства Буна 1959 года о том, что проблема слов для групп неразрешима. Он использует теоретико-групповой подход, в частности лемму Бриттона . Это доказательство использовалось в аспирантуре, хотя существуют более современные и сокращенные доказательства.
• 1977 ( 1977 ) : экзистенциальной теории уравнений над свободными моноидами . Геннадий Маканин доказывает разрешимость

Словесная задача для систем полутуэ

Проблему доступности для систем переписывания строк (полусистем Туэ или полугрупп) можно сформулировать следующим образом: для данной системы полуТуэ $T:=(\Sigma ,R)$ и два слова (строки) $u,v\in \Sigma ^{*}$, может $u$ превратиться в $v$ применяя правила из $R$? Обратите внимание, что переписывание здесь одностороннее. Проблема слов — это проблема доступности для симметричных отношений перезаписи, то есть систем Туэ.

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

Словесная задача для групп

Основная статья: Словесная задача для групп

Учитывая презентацию $\langle S\mid {\mathcal {R}}\rangle$ для группы G проблема слов — это алгоритмическая проблема решения, учитывая два входных слова из S и тот же элемент G. , представляют ли они один Проблема слов — одна из трех алгоритмических проблем для групп, предложенных Максом Деном показал В 1955 году Петр Новиков , что существует конечно представимая группа G такая, что проблема слов для G неразрешима в 1911 году . .

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

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

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

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

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

Решение словесной задачи: решить, если $x{\stackrel {*}{\leftrightarrow }}y$ обычно требуется эвристический поиск ( красный , зеленый ), пока решаю $x\downarrow =y\downarrow$ это просто( серый ).

Проблема слов для абстрактной системы переписывания (ARS) довольно лаконична: данные объекты x и y эквивалентны при ${\stackrel {*}{\leftrightarrow }}$? Словесная проблема для АРС неразрешима вообще . Однако существует вычислимое решение проблемы слов в конкретном случае, когда каждый объект приводится к уникальной нормальной форме за конечное число шагов (т. е. система сходится ) : два объекта эквивалентны при ${\stackrel {*}{\leftrightarrow }}$ тогда и только тогда, когда они приводятся к одной и той же нормальной форме. Алгоритм завершения Кнута-Бендикса можно использовать для преобразования набора уравнений в конвергентную систему переписывания термов .

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

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

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

Словесная задача для свободных решеток

Пример вычисления x ∧ z ~ x ∧ z ∧( x ∨ y )

x ∧ z ∧( x ∨ y ) ≤ ~ x ∧ z на 5. с x ∧ z ≤ ~ x ∧ z на 1. с x ∧ z = x ∧ z

x ∧ z ≤ ~ x ∧ z ∧( x ∨ y ) к 7. с x ∧ z ≤ ~ x ∧ z и x ∧ z ≤ ~ x ∨ y на 1. с x ∧ z = x ∧ z на 6. с x ∧ z ≤ ~ х на 5. с х ≤ ~ х на 1. с х = х

Проблема слов о свободных решетках и, в более общем плане, о свободных ограниченных решетках имеет разрешимое решение. Ограниченные решетки — это алгебраические структуры с двумя бинарными операциями ∨ и ∧ и двумя константами ( нулевыми операциями ) 0 и 1. Набор всех корректных выражений , которые можно сформулировать с помощью этих операций над элементами из заданного набора генераторов X, будет называться W ( X ). Этот набор слов содержит множество выражений, которые обозначают равные значения в каждой решетке. Например, если a — некоторый элемент X , то a ∨ 1 = 1 и a ∧ 1 = a . Проблема слов для свободных ограниченных решеток — это проблема определения того, какие из этих элементов W ( X ) обозначают один и тот же элемент в свободной ограниченной решетке FX и, следовательно, в каждой ограниченной решетке.

Словесную проблему можно решить следующим образом. Отношение ≤ _~ на W ( X ) может быть определено индуктивно , установив w ≤ _~ v тогда и только тогда, когда выполняется одно из следующих условий:

1.   w = v (это можно ограничить случаем, когда w и v являются элементами X ),
2.   ш = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ и выполняются оба w ₁ ≤ _~ v и w ₂ ≤ _~ v ,
5.   w = w ₁ ∧ w ₂ и либо w ₁ ≤ _~ v , либо w ₂ ≤ _~ v , выполняется
6.   v = v ₁ ∨ v ₂ и либо w ≤ _~ v _1, либо w ≤ _~ v _{2 ,} выполняется
7.   v = v ₁ ∧ v ₂ и выполняются оба условия w ≤ _~ v ₁ и w ≤ _~ v ₂ .

Это определяет предварительный порядок ≤ _~ на W ( X ), поэтому отношение эквивалентности может быть определено как w ~ v, когда w ≤ _~ v и v ≤ _~ w . Тогда можно показать, что частично упорядоченное фактормножество W ( X )/~ представляет собой свободную ограниченную решетку FX . Классы эквивалентности W ⩽ ( X это множества всех слов w и v с w ⩽ _~ v и v ~ _{)/~ —} w . Два правильно построенных слова v и w в W ( X ) обозначают одно и то же значение в каждой ограниченной решетке тогда и только тогда, когда w ≤ _~ v и v ≤ _~ w ; последние условия можно эффективно решить, используя приведенное выше индуктивное определение. В таблице показан пример вычисления, показывающий, что слова x ∧ z и x ∧ z ∧( x ∨ y ) обозначают одно и то же значение в каждой ограниченной решетке. Случай неограниченных решеток рассматривается аналогично, опуская правила 2 и 3 в приведенной выше конструкции ≤ _~ .

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

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

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

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

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

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

А1	$1\cdot x$	$=x$
А2	$x^{-1}\cdot x$	$=1$
А3	$(x\cdot y)\cdot z$	$=x\cdot (y\cdot z)$

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

Р1	$1\cdot x$	$\rightsquigarrow x$
Р2	$x^{-1}\cdot x$	$\rightsquigarrow 1$
Р3	$(x\cdot y)\cdot z$	$\rightsquigarrow x\cdot (y\cdot z)$
Р4	$x^{-1}\cdot (x\cdot y)$	$\rightsquigarrow y$
Р8	$1^{-1}$	$\rightsquigarrow 1$
Р11	$x\cdot 1$	$\rightsquigarrow x$
Р12	$(x^{-1})^{-1}$	$\rightsquigarrow x$
Р13	$x\cdot x^{-1}$	$\rightsquigarrow 1$
Р14	$x\cdot (x^{-1}\cdot y)$	$\rightsquigarrow y$
Р17	$(x\cdot y)^{-1}$	$\rightsquigarrow y^{-1}\cdot x^{-1}$

См. также

• Проблема сопряжения
• Проблема группового изоморфизма