В компьютерной алгебре часто требуется закодировать математические выражения с помощью дерева выражений. Но часто существует несколько эквивалентных деревьев выражений. Естественно возникает вопрос, существует ли алгоритм, который, учитывая два входных выражения, решает, представляют ли они один и тот же элемент. Такой алгоритм называется решением проблемы слова . Например, представьте, что это символы, представляющие действительные числа . Тогда подходящее решение проблемы со словами будет, учитывая входные данные , выдавать выходные данные и аналогичным образом производить результат из .EQUALNOT_EQUAL
Наиболее прямое решение проблемы со словами принимает форму теоремы и алгоритма нормальной формы, который отображает каждый элемент в классе эквивалентности выражений в одну кодировку, известную как нормальная форма . Затем проблема со словами решается путем сравнения этих нормальных форм с помощью синтаксическое равенство . [1] Например, можно решить, что это нормальная форма , и , и разработать систему преобразований для перезаписи этих выражений в эту форму, в процессе доказывая, что все эквивалентные выражения будут переписаны в одну и ту же нормальную форму. [2] Но не все решения проблемы слов используют теорему о нормальной форме — существуют алгебраические свойства, которые косвенно подразумевают существование алгоритма. [1]
В то время как проблема слов спрашивает, равны ли два термина, содержащих константы , правильное расширение проблемы слов, известное как проблема объединения, спрашивает, имеют ли два термина , содержащие переменные , равные экземпляры , или, другими словами , имеет ли уравнение какие-либо решения. Типичным примером является проблема со словами в целочисленной группе , а также проблема объединения в той же группе; поскольку первые члены оказываются равными в , последняя задача имеет замену в качестве решения.
История
Один из наиболее глубоко изученных случаев проблемы слова находится в теории полугрупп и групп . Хронология статей, имеющих отношение к теореме Новикова-Буна , следующая: [3] [4]
1910 : Аксель Туэ ставит общую проблему переписывания терминов в древовидных структурах. Он утверждает: «Решение этой проблемы в самом общем случае может быть связано, пожалуй, с непреодолимыми трудностями». [5] [6] ( 1910 )
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]
Проблемы доступности и слова неразрешимы , т.е. не существует общего алгоритма решения этой проблемы. [28] Это справедливо даже в том случае, если мы ограничим системы конечными представлениями, т. е. конечным набором символов и конечным набором отношений к этим символам. [27] Даже проблема слов, ограниченная основными терминами, неразрешима для некоторых конечно определенных полугрупп. [29] [30]
Словесная задача для групп
Учитывая представление группы G , проблема слов представляет собой алгоритмическую проблему решения, учитывая два входных слова в S , представляют ли они один и тот же элемент G. Проблема слов — одна из трех алгоритмических проблем для групп, предложенных Максом Деном в 1911 году. В 1955 году Петр Новиков показал, что существует конечно представимая группа G такая , что проблема слов для G неразрешима . [31]
Словесная проблема в комбинаторном исчислении и лямбда-исчислении
Одно из первых доказательств того, что проблема со словами неразрешима, было связано с комбинаторной логикой : когда две строки комбинаторов эквивалентны? Поскольку комбинаторы кодируют все возможные машины Тьюринга , а эквивалентность двух машин Тьюринга неразрешима, отсюда следует, что эквивалентность двух строк комбинаторов неразрешима. Алонсо Чёрч наблюдал это в 1936 году. [32]
Аналогично, по существу, та же проблема возникает в (нетипизированном) лямбда-исчислении : для двух различных лямбда-выражений не существует алгоритма, который мог бы определить, эквивалентны они или нет; эквивалентность неразрешима . Для нескольких типизированных вариантов лямбда-исчисления эквивалентность разрешима путем сравнения нормальных форм.
Проблема слов для абстрактных систем переписывания
Решение задачи со словами: решение, требуется ли обычно эвристический поиск ( красный , зеленый ), при этом решение является простым ( серый ).
Проблема слов для абстрактной системы переписывания (ARS) довольно лаконична: данные объекты x и y эквивалентны относительно ? [29] Проблема слов для АРС вообще неразрешима . Однако существует вычислимое решение проблемы слов в конкретном случае, когда каждый объект сводится к уникальной нормальной форме за конечное число шагов (т. е. система сходится ) : два объекта эквивалентны тогда и только тогда, когда они сводятся к та же нормальная форма. [33]
Алгоритм завершения Кнута-Бендикса можно использовать для преобразования набора уравнений в сходящуюся систему переписывания терминов .
Проблема слов в универсальной алгебре
В универсальной алгебре изучаются алгебраические структуры , состоящие из порождающего множества A , набора операций над A конечной арности и конечного набора тождеств, которым эти операции должны удовлетворять. Словесная проблема для алгебры состоит в том, чтобы по данным двум выражениям (словам), включающим генераторы и операции, определить, представляют ли они один и тот же элемент алгебры по модулю тождеств. Словесные задачи для групп и полугрупп можно сформулировать как словесные задачи для алгебр. [1]
Проблема слов на свободных алгебрах Гейтинга сложна. [34]
Единственные известные результаты состоят в том, что свободная алгебра Гейтинга на одном генераторе бесконечна и что свободная полная алгебра Гейтинга на одном генераторе существует (и имеет на один элемент больше, чем свободная алгебра Гейтинга).
Словесная задача для свободных решеток
Проблема слов о свободных решетках и, в более общем плане, о свободных ограниченных решетках имеет разрешимое решение. Ограниченные решетки — это алгебраические структуры с двумя бинарными операциями ∨ и ∧ и двумя константами ( нулевыми операциями ) 0 и 1. Набор всех корректных выражений , которые можно сформулировать с помощью этих операций над элементами из заданного набора генераторов X , будет называться W ( X ). Этот набор слов содержит множество выражений, которые обозначают равные значения в каждой решетке. Например, если a — некоторый элемент X , то a ∨ 1 = 1 и a ∧ 1 = a . Проблема слов для свободных ограниченных решеток — это проблема определения того, какие из этих элементов W ( X ) обозначают один и тот же элемент в свободной ограниченной решетке FX и, следовательно, в каждой ограниченной решетке.
Словесную проблему можно решить следующим образом. Отношение ≤ ~ на W ( X ) может быть определено индуктивно, установив w ≤ ~ v тогда и только тогда, когда выполняется одно из следующих условий:
w = v (это можно ограничить случаем, когда w и v являются элементами X ),
ш = 0,
v = 1,
w = w 1 ∨ w 2 и выполняются оба w 1 ≤ ~ v и w 2 ≤ ~ v ,
w = w 1 ∧ w 2 и выполняется либо w 1 ≤ ~ v , либо w 2 ≤ ~ v ,
v = v 1 ∨ v 2 и выполняется либо w ≤ ~ v 1 , либо w ≤ ~ v 2 ,
v = v 1 ∧ v 2 и выполняются оба условия w ≤ ~ v 1 и w ≤ ~ v 2 .
Это определяет предварительный порядок ≤ ~ на 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]
Правила перезаписи пронумерованы несмежными, поскольку некоторые правила стали избыточными и были удалены во время работы алгоритма. Равенство двух термов следует из аксиом тогда и только тогда, когда оба терма преобразуются буквально в один и тот же терм в нормальной форме. Например, условия
, и
имеют одну и ту же нормальную форму, а именно. ; следовательно, оба члена равны в каждой группе. Другой пример: член и имеет нормальную форму и соответственно. Поскольку нормальные формы буквально различны, исходные термины не могут быть одинаковыми в каждой группе. На самом деле в неабелевых группах они обычно различны .
^ abcd Эванс, Тревор (1978). "Текстовые задачи". Бюллетень Американского математического общества . 84 (5): 790. doi : 10.1090/S0002-9904-1978-14516-9 .
^ Коэн, Джоэл С. (2002). Компьютерная алгебра и символьные вычисления: элементарные алгоритмы . Натик, Массачусетс: АК Питерс. стр. 90–92. ISBN1568811586.
^ abcdefg Миллер, Чарльз Ф. (2014). Дауни, Род (ред.). «Машины Тьюринга для решения текстовых задач» (PDF) . Наследие Тьюринга : 330. doi : 10.1017/CBO9781107338579.010. hdl : 11343/51723. ISBN9781107338579. Проверено 6 декабря 2021 г.
^ Стиллвелл, Джон (1982). «Проблема слов и проблема изоморфизма групп». Бюллетень Американского математического общества . 6 (1): 33–56. дои : 10.1090/S0273-0979-1982-14963-1 .
↑ Мюллер-Штах, Стефан (12 сентября 2021 г.). «Макс Ден, Аксель Туэ и неразрешимое». п. 13. arXiv : 1703.09750 [math.HO].
^ Стейнби, Магнус; Томас, Вольфганг (2000). «Деревья и переписывание терминов в 1910 году: на бумаге Акселя Туэ». Бюллетень Европейской ассоциации теоретической информатики . 72 : 256–269. CiteSeerX 10.1.1.32.8993 . МР 1798015.
^ Гриндлингер, Мартин (июнь 1959 г.). «Алгоритм Дена для решения проблемы слов». Сообщения по чистой и прикладной математике . 13 (1): 67–83. дои : 10.1002/cpa.3160130108.
^ Шупп, Пол Э. (июнь 1968 г.). «Об алгоритме Дена и проблеме сопряженности». Математические Аннален . 178 (2): 119–130. дои : 10.1007/BF01350654. S2CID 120429853.
↑ Пауэр, Джеймс Ф. (27 августа 2013 г.). «Документ Туэ 1914 года: перевод». arXiv : 1308.5858 [cs.FL].
^ Пост, Эмиль Л. (март 1947 г.). «Рекурсивная неразрешимость проблемы Туэ» (PDF) . Журнал символической логики . 12 (1): 1–11. дои : 10.2307/2267170. JSTOR 2267170. S2CID 30320278 . Проверено 6 декабря 2021 г.
^ Мостовский, Анджей (сентябрь 1951 г.). "А. Марков. Невозможность некоторых алгоритмов в теории ассоциативных систем. Доклады Академии наук СССР, т. 77 (1951), стр. 19–20". Журнал символической логики . 16 (3): 215. дои : 10.2307/2266407. JSTOR 2266407.
^ Тьюринг, AM (сентябрь 1950 г.). «Словная задача в полугруппах с отменой». Анналы математики . 52 (2): 491–505. дои : 10.2307/1969481. JSTOR 1969481.
^ Бун, Уильям В. (1954). «Некоторые простые неразрешимые проблемы теории групп. I». Indagationes Mathematicae (Труды) . 57 : 231–237. дои : 10.1016/S1385-7258(54)50033-8.
^ Бун, Уильям В. (1957). «Некоторые простые неразрешимые проблемы теории групп. VI». Indagationes Mathematicae (Труды) . 60 : 227–232. дои : 10.1016/S1385-7258(57)50030-9 .
^ Бриттон, JL (октябрь 1958 г.). «Словопроблема для групп». Труды Лондонского математического общества . с3-8 (4): 493–506. дои : 10.1112/plms/s3-8.4.493.
^ Бун, Уильям В. (1958). «Проблема слова» (PDF) . Труды Национальной академии наук . 44 (10): 1061–1065. Бибкод : 1958PNAS...44.1061B. дои : 10.1073/pnas.44.10.1061 . ПМК 528693 . PMID 16590307. Збл 0086.24701.
^ Бун, Уильям В. (сентябрь 1959 г.). «Проблема слова». Анналы математики . 70 (2): 207–265. дои : 10.2307/1970103. JSTOR 1970103.
^ Хигман, Г. (8 августа 1961 г.). «Подгруппы конечно определенных групп». Труды Лондонского королевского общества. Серия А. Математические и физические науки . 262 (1311): 455–475. Бибкод : 1961RSPSA.262..455H. дои : 10.1098/rspa.1961.0132. S2CID 120100270.
^ Бриттон, Джон Л. (январь 1963 г.). «Проблема слова». Анналы математики . 77 (1): 16–32. дои : 10.2307/1970200. JSTOR 1970200.
↑ Симпсон, Стивен Г. (18 мая 2005 г.). «Лучшее доказательство неразрешимости проблемы слов для конечно представленных групп» (PDF) . Проверено 6 декабря 2021 г.
^ «Подгруппы конечно представленных групп». Математика СССР-Сборник . 103 (145): 147–236. 13 февраля 1977 г. doi : 10.1070/SM1977v032n02ABEH002376.
^ аб Матиясевич, Юрий; Сенизерг, Жеро (январь 2005 г.). «Задачи решения для систем полуТуэ с несколькими правилами». Теоретическая информатика . 330 (1): 145–169. дои : 10.1016/j.tcs.2004.09.016 .
^ Дэвис, Мартин (1978). «Что такое вычисление?» (PDF) . Математика сегодня Двенадцать неформальных эссе : 257–259. дои : 10.1007/978-1-4613-9435-8_10. ISBN978-1-4613-9437-2. Проверено 5 декабря 2021 г.
^ Аб Баадер, Франц; Нипков, Тобиас (5 августа 1999 г.). Переписывание терминов и все такое. Издательство Кембриджского университета. стр. 59–60. ISBN978-0-521-77920-3.
^
Матиясевич, Ю. В. (1967). «Простые примеры неразрешимых ассоциативных исчислений». Доклады Академии наук СССР . 173 (6): 1264–1266. ISSN 0869-5652.
Матиясевич, Ю. В. (1967). «Простые примеры неразрешимых ассоциативных исчислений». Советская математика . 8 (2): 555–557. ISSN 0197-6788.
^ Новиков, П. С. (1955). «Об алгоритмической неразрешимости проблемы слов в теории групп». Труди Мат. Инст. Стеклов (на русском языке). 44 : 1–143.
^ Статман, Рик (2000). «О проблеме слов для комбинаторов». Техники и приложения переписывания . Конспекты лекций по информатике. 1833 : 203–213. дои : 10.1007/10721975_14. ISBN978-3-540-67778-9.
^ Беке, Тибор (май 2011 г.). «Категоризация, переписывание терминов и процедура Кнута – Бендикса». Журнал чистой и прикладной алгебры . 215 (5): 730. doi : 10.1016/j.jpaa.2010.06.019 .
^ Питер Т. Джонстон, Stone Spaces , (1982) Издательство Кембриджского университета, Кембридж, ISBN 0-521-23893-5 . (См. главу 1, параграф 4.11)
^ Уитмен, Филип М. (январь 1941 г.). «Свободные решетки». Анналы математики . 42 (1): 325–329. дои : 10.2307/1969001. JSTOR 1969001.
^ Уитмен, Филип М. (1942). «Свободные решетки II». Анналы математики . 43 (1): 104–115. дои : 10.2307/1968883. JSTOR 1968883.
^ К. Х. Блазиус и Х.-Ю. Бюркерт, изд. (1992). Система вычетов . Ольденбург. п. 291.; здесь: стр.126, 134
^ Применяйте правила в любом порядке к термину как можно дольше; результат не зависит от заказа; это нормальная форма термина.