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

Проблема решения, относящаяся к эквивалентности выражений

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

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

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

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

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

История

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

• 1910 : Аксель Туэ ставит общую проблему переписывания терминов в древовидных структурах. Он утверждает: «Решение этой проблемы в самом общем случае может быть связано, пожалуй, с непреодолимыми трудностями». ^{[5] [6]} ( 1910 )
• 1911 : Макс Ден ставит проблему слов для конечно представленных групп . ^[7] (1911)
• 1912 : Ден представляет алгоритм Дена и доказывает, что он решает проблему слов для фундаментальных групп замкнутых ориентируемых двумерных многообразий рода больше или равного 2. ^[8] Последующие авторы значительно расширили его на широкий диапазон групповых многообразий. теоретические проблемы решения. ^{[9] [10] [11]} (1912)
• 1914 : Аксель Туэ ставит проблему слов для конечно определенных полугрупп. ^[12] (1914)
• 1930–1938 : Возникает тезис Чёрча-Тьюринга ,  определяющий формальные понятия вычислимости и неразрешимости. ^[13] (1930) (1938)
• 1947 : Эмиль Пост и Андрей Марков-младший независимо друг от друга строят конечно определенные полугруппы с неразрешимой проблемой слов. ^{[14] [15]} Конструкция Поста построена на машинах Тьюринга, тогда как конструкция Маркова использует обычные системы Поста. ^[3] (1947)
• 1950 : Алан Тьюринг показывает, что проблема слов для полугрупп сокращения неразрешима, ^[16] , развивая конструкцию Поста. Доказательство трудно понять, но оно знаменует собой поворотный момент в проблеме слов для групп. ^{[3] : 342} (1950)
• 1955 : Петр Новиков дает первое опубликованное доказательство неразрешимости проблемы слов для групп, используя результат Тьюринга о сокращении полугруппы. ^{[17] [3] : 354} Доказательство содержит «Основную лемму», эквивалентную лемме Бриттона . ^{[3] : 355} (1955)
• 1954–1957 : Уильям Бун независимо показывает  , что проблема слов для групп неразрешима, используя конструкцию полугруппы Поста. ^{[18] [19]} (1954) (1957)
• 1957–1958 : Джон Бриттон дает еще одно доказательство неразрешимости проблемы слов для групп, основанное на результате Тьюринга о полугруппах о сокращении и некоторых более ранних работах Бриттона  . ^[20] Появляется ранняя версия леммы Бриттона. ^{[3] : 355} (1957) (1958)
• 1958–1959 :  Бун публикует упрощенную версию своей конструкции. ^{[21] [22]} (1958) (1959)
• 1961 : Грэм Хигман характеризует подгруппы конечно представленных групп с помощью теоремы вложения Хигмана , ^[23] неожиданным образом соединяя теорию рекурсии с теорией групп и давая совершенно иное доказательство неразрешимости проблемы слов. ^[3] (1961)
• 1961–1963 : Бриттон представляет значительно упрощенную версию доказательства Буна  1959 года о неразрешимости проблемы слов для групп. ^[24] Он использует теоретико-групповой подход, в частности лемму Бриттона . Это доказательство использовалось в аспирантуре, хотя существуют более современные и сокращенные доказательства. ^[25] (1961) (1963)
• 1977 : Геннадий Маканин доказывает разрешимость экзистенциальной теории уравнений над свободными моноидами . ^[26] (1977)

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

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

Проблемы доступности и слова неразрешимы , т.е. не существует общего алгоритма решения этой проблемы. ^[28] Это справедливо даже в том случае, если мы ограничим системы конечными представлениями, т. е. конечным набором символов и конечным набором отношений к этим символам. ^[27] Даже проблема слов, ограниченная основными терминами, неразрешима для некоторых конечно определенных полугрупп. ^{[29] [30]}

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

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

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

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

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

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

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

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

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

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

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

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

Проблема слов о свободных решетках и, в более общем плане, о свободных ограниченных решетках имеет разрешимое решение. Ограниченные решетки — это алгебраические структуры с двумя бинарными операциями ∨ и ∧ и двумя константами ( нулевыми операциями ) 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 ₁ , либо w ≤ _~ v _{2 ,}
7.   v = v ₁ ∧ v ₂ и выполняются оба условия w ≤ _~ v ₁ и w ≤ _~ v ₂ .

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

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

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

${\displaystyle ((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}$, и

${\displaystyle 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}$

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

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

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

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

1. Эванс, Тревор (1978). "Текстовые задачи". Бюллетень Американского математического общества . 84 (5): 790. doi : 10.1090/S0002-9904-1978-14516-9 .
2. Коэн, Джоэл С. (2002). Компьютерная алгебра и символьные вычисления: элементарные алгоритмы . Натик, Массачусетс: АК Питерс. стр. 90–92. ISBN 1568811586.
3. Миллер, Чарльз Ф. (2014). Дауни, Род (ред.). «Машины Тьюринга для решения текстовых задач» (PDF) . Наследие Тьюринга : 330. doi : 10.1017/CBO9781107338579.010. hdl : 11343/51723. ISBN 9781107338579. Проверено 6 декабря 2021 г.
4. Стиллвелл, Джон (1982). «Проблема слов и проблема изоморфизма групп». Бюллетень Американского математического общества . 6 (1): 33–56. дои : 10.1090/S0273-0979-1982-14963-1 .
5. Мюллер-Штах, Стефан (12 сентября 2021 г.). «Макс Ден, Аксель Туэ и неразрешимое». п. 13. arXiv : 1703.09750 [math.HO].
6. Стейнби, Магнус; Томас, Вольфганг (2000). «Деревья и переписывание терминов в 1910 году: на бумаге Акселя Туэ». Бюллетень Европейской ассоциации теоретической информатики . 72 : 256–269. CiteSeerX 10.1.1.32.8993 . МР  1798015. 
7. Ден, Макс (1911). «Über unendliche disontinuierliche Gruppen». Математические Аннален . 71 (1): 116–144. дои : 10.1007/BF01456932. ISSN  0025-5831. MR  1511645. S2CID  123478582.
8. Ден, Макс (1912). «Трансформация Курвена на свежем воздухе». Математические Аннален . 72 (3): 413–421. дои : 10.1007/BF01456725. ISSN  0025-5831. MR  1511705. S2CID  122988176.
9. Гриндлингер, Мартин (июнь 1959 г.). «Алгоритм Дена для решения проблемы слов». Сообщения по чистой и прикладной математике . 13 (1): 67–83. дои : 10.1002/cpa.3160130108.
10. Линдон, Роджер К. (сентябрь 1966 г.). «Об алгоритме Дена». Математические Аннален . 166 (3): 208–228. дои : 10.1007/BF01361168. hdl : 2027.42/46211 . S2CID  36469569.
11. Шупп, Пол Э. (июнь 1968 г.). «Об алгоритме Дена и проблеме сопряженности». Математические Аннален . 178 (2): 119–130. дои : 10.1007/BF01350654. S2CID  120429853.
12. Пауэр, Джеймс Ф. (27 августа 2013 г.). «Документ Туэ 1914 года: перевод». arXiv : 1308.5858 [cs.FL].
13. См. « История церкви – диссертация Тьюринга» . Даты основаны на формально неразрешимых положениях Principia Mathematica и связанных с ними систем и систем логики, основанных на порядковых числах .
14. Пост, Эмиль Л. (март 1947 г.). «Рекурсивная неразрешимость проблемы Туэ» (PDF) . Журнал символической логики . 12 (1): 1–11. дои : 10.2307/2267170. JSTOR  2267170. S2CID  30320278 . Проверено 6 декабря 2021 г.
15. Мостовский, Анджей (сентябрь 1951 г.). "А. Марков. Невозможность некоторых алгоритмов в теории ассоциативных систем. Доклады Академии наук СССР, т. 77 (1951), стр. 19–20". Журнал символической логики . 16 (3): 215. дои : 10.2307/2266407. JSTOR  2266407.
16. Тьюринг, AM (сентябрь 1950 г.). «Словная задача в полугруппах с отменой». Анналы математики . 52 (2): 491–505. дои : 10.2307/1969481. JSTOR  1969481.
17. Новиков, П. С. (1955). «Об алгоритмической неразрешимости проблемы слов в теории групп». Известия Математического института им. Стеклова (на русском языке). 44 : 1–143. Збл  0068.01301.
18. Бун, Уильям В. (1954). «Некоторые простые неразрешимые проблемы теории групп. I». Indagationes Mathematicae (Труды) . 57 : 231–237. дои : 10.1016/S1385-7258(54)50033-8.
19. Бун, Уильям В. (1957). «Некоторые простые неразрешимые проблемы теории групп. VI». Indagationes Mathematicae (Труды) . 60 : 227–232. дои : 10.1016/S1385-7258(57)50030-9 .
20. Бриттон, JL (октябрь 1958 г.). «Словопроблема для групп». Труды Лондонского математического общества . с3-8 (4): 493–506. дои : 10.1112/plms/s3-8.4.493.
21. Бун, Уильям В. (1958). «Проблема слова» (PDF) . Труды Национальной академии наук . 44 (10): 1061–1065. Бибкод : 1958PNAS...44.1061B. дои : 10.1073/pnas.44.10.1061 . ПМК 528693 . PMID  16590307. Збл  0086.24701. 
22. Бун, Уильям В. (сентябрь 1959 г.). «Проблема слова». Анналы математики . 70 (2): 207–265. дои : 10.2307/1970103. JSTOR  1970103.
23. Хигман, Г. (8 августа 1961 г.). «Подгруппы конечно определенных групп». Труды Лондонского королевского общества. Серия А. Математические и физические науки . 262 (1311): 455–475. Бибкод : 1961RSPSA.262..455H. дои : 10.1098/rspa.1961.0132. S2CID  120100270.
24. Бриттон, Джон Л. (январь 1963 г.). «Проблема слова». Анналы математики . 77 (1): 16–32. дои : 10.2307/1970200. JSTOR  1970200.
25. Симпсон, Стивен Г. (18 мая 2005 г.). «Лучшее доказательство неразрешимости проблемы слов для конечно представленных групп» (PDF) . Проверено 6 декабря 2021 г.
26. «Подгруппы конечно представленных групп». Математика СССР-Сборник . 103 (145): 147–236. 13 февраля 1977 г. doi : 10.1070/SM1977v032n02ABEH002376.
27. Матиясевич, Юрий; Сенизерг, Жеро (январь 2005 г.). «Задачи решения для систем полуТуэ с несколькими правилами». Теоретическая информатика . 330 (1): 145–169. дои : 10.1016/j.tcs.2004.09.016 .
28. Дэвис, Мартин (1978). «Что такое вычисление?» (PDF) . Математика сегодня Двенадцать неформальных эссе : 257–259. дои : 10.1007/978-1-4613-9435-8_10. ISBN 978-1-4613-9437-2. Проверено 5 декабря 2021 г.
29. Баадер, Франц; Нипков, Тобиас (5 августа 1999 г.). Переписывание терминов и все такое. Издательство Кембриджского университета. стр. 59–60. ISBN 978-0-521-77920-3.
30. • Матиясевич, Ю. В. (1967). «Простые примеры неразрешимых ассоциативных исчислений». Доклады Академии наук СССР . 173 (6): 1264–1266. ISSN  0869-5652.
    • Матиясевич, Ю. В. (1967). «Простые примеры неразрешимых ассоциативных исчислений». Советская математика . 8 (2): 555–557. ISSN  0197-6788.
31. Новиков, П. С. (1955). «Об алгоритмической неразрешимости проблемы слов в теории групп». Труди Мат. Инст. Стеклов (на русском языке). 44 : 1–143.
32. Статман, Рик (2000). «О проблеме слов для комбинаторов». Техники и приложения переписывания . Конспекты лекций по информатике. 1833 : 203–213. дои : 10.1007/10721975_14. ISBN 978-3-540-67778-9.
33. Беке, Тибор (май 2011 г.). «Категоризация, переписывание терминов и процедура Кнута – Бендикса». Журнал чистой и прикладной алгебры . 215 (5): 730. doi : 10.1016/j.jpaa.2010.06.019 .
34. Питер Т. Джонстон, Stone Spaces , (1982) Издательство Кембриджского университета, Кембридж, ISBN 0-521-23893-5 . (См. главу 1, параграф 4.11) 
35. Уитмен, Филип М. (январь 1941 г.). «Свободные решетки». Анналы математики . 42 (1): 325–329. дои : 10.2307/1969001. JSTOR  1969001.
36. Уитмен, Филип М. (1942). «Свободные решетки II». Анналы математики . 43 (1): 104–115. дои : 10.2307/1968883. JSTOR  1968883.
37. К. Х. Блазиус и Х.-Ю. Бюркерт, изд. (1992). Система вычетов . Ольденбург. п. 291.; здесь: стр.126, 134
38. Применяйте правила в любом порядке к термину как можно дольше; результат не зависит от заказа; это нормальная форма термина.