WikiDer > Система Semi-Thue

В теоретическая информатика и математическая логика а система перезаписи строк (SRS), исторически называемый полу-Чт система, это переписывание система над струны из (обычно конечный) алфавит. Учитывая бинарное отношение ${ displaystyle R}$ между фиксированными строками в алфавите, называемыми переписать правила, обозначаемый ${ displaystyle s rightarrow t}$, SRS расширяет отношение перезаписи на все строки, в которых левая и правая части правил отображаются как подстроки, то есть ${ displaystyle usv rightarrow utv}$, куда ${ displaystyle s}$, ${ displaystyle t}$, ${ displaystyle u}$, и ${ displaystyle v}$ струны.

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

SRS можно определить непосредственно как абстрактная система переписывания. Это также можно рассматривать как ограниченный вид переписывание терминов система. Как формализм, системы перезаписи строк Тьюринг завершен.^{[нужна цитата]} Название полу-Туэ происходит от норвежского математика. Аксель Туэ, который представил систематическое рассмотрение систем перезаписи строк в статье 1914 года.^[1] Туэ ввел это понятие в надежде решить проблему слов для конечно определенных полугрупп. Только в 1947 году проблема оказалась неразрешимый- этот результат был получен независимо Эмиль Пост и Марков А.А. Младший^[2][3]

Определение

А система перезаписи строк или же система полутхуэ это кортеж ${ Displaystyle ( Sigma, R)}$ куда

• Σ представляет собой алфавит, обычно предполагаемый конечным.^[4] Элементы набора ${ Displaystyle Sigma ^ {*}}$ (* это Клини звезда здесь) - конечные (возможно, пустые) строки на Σиногда называют слова в формальные языки; мы будем называть их здесь просто строками.
• р это бинарное отношение на струнах из Σ, т.е. ${ Displaystyle R substeq Sigma ^ {*} times Sigma ^ {*}.}$ Каждый элемент ${ displaystyle (u, v) in R}$ называется (переписывание) правило и обычно пишется ${ displaystyle u rightarrow v}$.

Если отношение р является симметричный, то система называется Система Туэ.

Правила перезаписи в р может быть естественным образом расширен на другие строки в ${ Displaystyle Sigma ^ {*}}$ позволяя переписывать подстроки в соответствии с р. Более формально отношение одноэтапной перезаписи связь ${ displaystyle { xrightarrow [{R}] {}}}$ индуцированный р на ${ Displaystyle Sigma ^ {*}}$ для любых струн ${ displaystyle s, т in Sigma ^ {*}}$:

${ displaystyle s { xrightarrow [{R}] {}} t}$ тогда и только тогда, когда существуют ${ Displaystyle х, у, и, v in Sigma ^ {*}}$ такой, что ${ displaystyle s = xuy}$, ${ displaystyle t = xvy}$, и ${ displaystyle u rightarrow v}$.

С ${ displaystyle { xrightarrow [{R}] {}}}$ это отношение на ${ Displaystyle Sigma ^ {*}}$, пара ${ Displaystyle ( Sigma ^ {*}, { xrightarrow [{R}] {}})}$ подходит под определение абстрактная система переписывания. Очевидно р это подмножество ${ displaystyle { xrightarrow [{R}] {}}}$. Некоторые авторы используют другое обозначение стрелки в ${ displaystyle { xrightarrow [{R}] {}}}$ (например. ${ displaystyle { xrightarrow [{R}] {}}}$), чтобы отличить его от р сам (${ displaystyle rightarrow}$), потому что позже они захотят убрать нижний индекс и при этом избежать путаницы между р и одношаговая перезапись, вызванная р.

Ясно, что в системе полутуэ мы можем сформировать (конечную или бесконечную) последовательность струн, образованную, начиная с начальной строки ${ displaystyle s_ {0} in Sigma ^ {*}}$ и многократно переписывая его, заменяя одну подстроку за раз:

${ Displaystyle s_ {0} { xrightarrow [{R}] {}} s_ {1} { xrightarrow [{R}] {}} s_ {2} { xrightarrow [{R}] {}} ldots}$

Переписывание с нулевым или большим количеством шагов, подобное этому, фиксируется рефлексивное переходное замыкание из ${ displaystyle { xrightarrow [{R}] {}}}$, обозначаемый ${ displaystyle { xrightarrow [{R}] {*}}}$ (видеть абстрактная система переписывания # Основные понятия). Это называется переписывающее отношение или же редукционное отношение на ${ Displaystyle Sigma ^ {*}}$ индуцированный р.

Thue congruence

В общем, набор ${ Displaystyle Sigma ^ {*}}$ строк в алфавите образует свободный моноид вместе с бинарная операция из конкатенация строк (обозначается как ${ displaystyle cdot}$ и записывается мультипликативно, отбрасывая символ). В SRS редукционное отношение ${ displaystyle { xrightarrow [{R}] {*}}}$ совместим с операцией моноида, что означает, что ${ displaystyle x { xrightarrow [{R}] {*}} y}$ подразумевает ${ displaystyle uxv { xrightarrow [{R}] {*}} uyv}$ для всех струн ${ Displaystyle х, у, и, v in Sigma ^ {*}}$. С ${ displaystyle { xrightarrow [{R}] {*}}}$ по определению Предварительный заказ, ${ displaystyle left ( Sigma ^ {*}, cdot, { xrightarrow [{R}] {*}} right)}$ образует моноидальный предзаказ.

Точно так же рефлексивное транзитивное симметричное замыкание из ${ displaystyle { xrightarrow [{R}] {}}}$, обозначенный ${ displaystyle { overset {*} { underset {R} { leftrightarrow}}}}$ (видеть абстрактная система переписывания # Основные понятия), это соответствие, то есть это отношение эквивалентности (по определению), и он также совместим с конкатенацией строк. Соотношение ${ displaystyle { overset {*} { underset {R} { leftrightarrow}}}}$ называется Thue congruence создано р. В системе Туэ, т.е. если р симметрично, соотношение перезаписи ${ displaystyle { xrightarrow [{R}] {*}}}$ совпадает с конгруэнцией Туэ ${ displaystyle { overset {*} { underset {R} { leftrightarrow}}}}$.

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

С ${ displaystyle { overset {*} { underset {R} { leftrightarrow}}}}$ является конгруэнцией, мы можем определить факторный моноид ${ displaystyle { mathcal {M}} _ {R} = Sigma ^ {*} / { overset {*} { underset {R} { leftrightarrow}}}}$ из свободный моноид ${ Displaystyle Sigma ^ {*}}$ по конгруэнции Туэ в обычная манера. Если моноид ${ Displaystyle { mathcal {M}}}$ является изоморфный с ${ displaystyle { mathcal {M}} _ {R}}$, то система полутуэ ${ Displaystyle ( Sigma, R)}$ называется моноидное представление из ${ Displaystyle { mathcal {M}}}$.

Мы сразу получаем очень полезные связи с другими областями алгебры. Например, алфавит {а, б} с правилами { ab → ε, ба → ε}, где ε - пустой строкой, представляет собой презентацию свободная группа на одном генераторе. Если вместо этого правила просто { ab → ε}, то мы получаем представление бициклический моноид.

Важность систем полу-Туэ как представления моноидов усиливается следующим:

Теорема: Каждый моноид имеет представление в виде ${ Displaystyle ( Sigma, R)}$, таким образом, он всегда может быть представлен полу-системой Туэ, возможно, над бесконечным алфавитом.^[5]

В этом контексте набор ${ displaystyle Sigma}$ называется набор генераторов из ${ Displaystyle { mathcal {M}}}$, и ${ displaystyle R}$ называется набором определение отношений ${ Displaystyle { mathcal {M}}}$. Мы можем сразу классифицировать моноиды на основе их представления. ${ Displaystyle { mathcal {M}}}$ называется

• конечно порожденный если ${ displaystyle Sigma}$ конечно.
• конечно представленный если оба ${ displaystyle Sigma}$ и ${ displaystyle R}$ конечны.

Проблема слов для систем полу-Туэ

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

Мартин Дэвис предлагает обычному читателю двухстраничное доказательство в своей статье «Что такое вычисления?» С. 258–259 с комментарием с. 257. Дэвис приводит доказательство следующим образом: «Придумайте [словесную проблему], решение которой привело бы к решению проблемы. проблема остановки."

Связи с другими понятиями

Система полутуэ также является переписывание терминов система - та, которая имеет монадический слова (функции), оканчивающиеся той же переменной, что и термины в левой и правой частях,^[6] например правило срока ${ displaystyle f_ {2} (f_ {1} (x)) rightarrow g (x)}$ эквивалентно строковому правилу ${ displaystyle f_ {1} f_ {2} rightarrow g}$.

Система полутхуэ также является особым типом Постканоническая система, но любую каноническую систему Post также можно свести к SRS. Оба формализма Тьюринг завершен, и, таким образом, эквивалентно Ноам Хомскийс неограниченная грамматика, которые иногда называют полутхуэ грамматики.^[7] А формальная грамматика только отличается от полутуэйской системы разделением алфавита на терминалы и нетерминалы, и фиксация начального символа среди нетерминалов. Меньшинство авторов фактически определяет систему полутуэ как тройную ${ Displaystyle ( Sigma, A, R)}$, куда ${ Displaystyle А substeq Sigma ^ {*}}$ называется набор аксиом. Согласно этому «порождающему» определению системы полутуэ, неограниченная грамматика - это просто система полутуэ с единственной аксиомой, в которой алфавит разбивается на терминальные и нетерминальные и делает аксиому нетерминальной.^[8] Простая уловка разделения алфавита на терминалы и нетерминалы - очень мощный прием; это позволяет определить Иерархия Хомского на основе того, какую комбинацию терминалов и нетерминалов содержат правила. Это было решающим достижением в теории формальные языки.

В квантовых вычислениях можно развить понятие квантовой системы Туэ.^[9]Поскольку квантовые вычисления по сути обратимы, правила перезаписи по алфавиту ${ displaystyle Sigma}$ должны быть двунаправленными (т. е. базовая система является системой Туэ, а не системой полу-Туэ). На подмножестве букв алфавита ${ Displaystyle Q substeq Sigma}$ можно присоединить гильбертово пространство ${ Displaystyle mathbb {C} ^ {d}}$, и правило перезаписи, переводящее одну подстроку в другую, может выполнять унитарную операцию над тензорным произведением гильбертова пространства, присоединенного к строкам; это означает, что они сохраняют количество символов из набора ${ displaystyle Q}$. Подобно классическому случаю можно показать, что квантовая система Туэ представляет собой универсальную вычислительную модель для квантовых вычислений в том смысле, что выполняемые квантовые операции соответствуют унифицированным классам схем (например, в BQP когда например гарантирующий завершение правил перезаписи строки в пределах полиномиально большого количества шагов от входного размера), или, что эквивалентно Квантовая машина Тьюринга.

История и значение

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

По предложению Церковь Алонсо, Эмиль Пост в статье, опубликованной в 1947 году, впервые доказал неразрешимость «определенной проблемы Туэ», что Мартин Дэвис заявляет как «... первое доказательство неразрешимости проблемы из классической математики - в данном случае слово проблема для полугрупп».^[10]

Дэвис также утверждает, что доказательство было независимо предложено Марков А.А..^[11]

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

• L-система
• MU головоломка

Примечания

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

Монографии

• Рональд В. Книга и Фридрих Отто, Системы перезаписи строк, Springer, 1993, ISBN 0-387-97965-4.
• Маттиас Янцен, Переписывание сливной строки, Birkhäuser, 1988, ISBN 0-387-13715-7.

Учебники

• Мартин Дэвис, Рон Сигал, Элейн Дж. Вейкер, Вычислимость, сложность и языки: основы теоретической информатики, 2-е изд., Academic Press, 1994, ISBN 0-12-206382-1, глава 7
• Элейн Рич, Автоматы, вычислимость и сложность: теория и приложения, Прентис Холл, 2007, ISBN 0-13-228806-0, глава 23.5.

Обзоры

• Самсон Абрамский, Дов М. Габбай, Томас С. Э. Майбаум (ред.), Справочник по логике в компьютерных науках: семантическое моделирование, Oxford University Press, 1995, ISBN 0-19-853780-8.
• Гжегож Розенберг, Арто Саломаа (ред.), Справочник формальных языков: слово, язык, грамматика, Springer, 1997 г., ISBN 3-540-60420-0.

Landmark документы

• Эмиль Пост (1947) Рекурсивная неразрешимость проблемы Туэ., Журнал символической логики 12: 1–11 через Проект Евклид.