Система Полу-Туэ

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

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

SRS можно определить непосредственно как абстрактную систему переписывания . Ее также можно рассматривать как ограниченную разновидность системы переписывания терминов , в которой все функциональные символы имеют арность не более 1. Как формализм, системы переписывания строк являются полными по Тьюрингу . Имя полу-Туэ происходит от норвежского математика Акселя Туэ , который представил систематическое рассмотрение систем переписывания строк в статье 1914 года. Туэ ввел это понятие в надежде решить проблему слов для конечно определенных полугрупп. задачи Лишь в 1947 году была показана неразрешимость — этот результат был получен независимо Эмилем Постом и А. А. Марковым-младшим.

Определение

Система переписывания строк или система полу-Туэ представляет собой кортеж. $(\Sigma ,R)$ где

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

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

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

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

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

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

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

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

Туэ конгруэнтность

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

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

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

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

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

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

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

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

• конечно порождено, если $\Sigma$ конечно.
• конечно представлено, если оба $\Sigma$ и $R$ конечны.

Неразрешимость проблемы слова

Пост доказал, что проблема слов (для полугрупп) в целом неразрешима, по существу, путем уменьшения проблемы остановки. для машин Тьюринга к примеру слова «проблема».

Конкретно, Пост разработал кодировку как конечную строку состояния машины Тьюринга плюс ленту, так что действия этой машины могут выполняться системой перезаписи строк, действующей на эту кодировку строки. Алфавит кодировки имеет один набор букв $S_{0},S_{1},\dotsc ,S_{m}$ для символов на ленте (где $S_{0}$ означает «пусто»), другой набор букв $q_{1},\dotsc ,q_{r}$ для состояний машины Тьюринга и, наконец, три буквы $q_{r+1},q_{r+2},h$ которые играют особую роль в кодировании. $q_{r+1}$ и $q_{r+2}$ интуитивно являются дополнительными внутренними состояниями машины Тьюринга, в которые она переходит при остановке, тогда как $h$ отмечает конец непустой части ленты; машина достигает $h$ должно вести себя так же, как если бы там была пустота, а $h$ находился в соседней камере. Строки, которые являются допустимыми кодировками состояний машины Тьюринга, начинаются с $h$, за которым следует ноль или более букв-символов, за которыми следует ровно одна буква внутреннего состояния $q_{i}$ (который кодирует состояние машины), за которым следует одна или несколько букв-символов, за которыми следует окончание $h$. Буквы-символы взяты непосредственно из содержимого ленты, а буква внутреннего состояния обозначает положение головы; символ после буквы внутреннего состояния — это символ, находящийся в ячейке под головкой машины Тьюринга.

Переход, при котором машина, находясь в состоянии $q_{i}$ и увидев символ $S_{k}$ записывает символ ответа $S_{l}$, перемещается вправо и переходит в состояние $q_{j}$ реализуется путем перезаписи

$q_{i}S_{k}\to S_{l}q_{j}$

тогда как этот переход вместо перемещения влево реализуется перезаписью

$S_{p}q_{i}S_{k}\to q_{j}S_{p}S_{l}$

с одним экземпляром для каждого символа $S_{p}$ в той камере слева. В случае, если мы дошли до конца посещенной части ленты, вместо этого используем

$hq_{i}S_{k}\to hq_{j}S_{0}S_{l}$,

удлинение строки на одну букву. Потому что все переписывания включают в себя одно внутреннее письмо о состоянии. $q_{i}$, действительные кодировки содержат только одну такую ​​букву, и каждая перезапись создает ровно одну такую ​​букву, процесс перезаписи точно соответствует запуску закодированной машины Тьюринга. Это доказывает, что системы перезаписи строк являются полными по Тьюрингу.

Причина наличия двух остановленных символов $q_{r+1}$ и $q_{r+2}$ заключается в том, что мы хотим, чтобы все останавливающиеся машины Тьюринга завершали работу в одном и том же общем состоянии, а не только в определенном внутреннем состоянии. Для этого необходимо очистить ленту после остановки, поэтому $q_{r+1}$ съедает символ слева, пока не достигнет $h$, где он переходит в $q_{r+2}$ который вместо этого съедает символ справа от себя. (На этом этапе система перезаписи строк больше не имитирует машину Тьюринга, поскольку она не может удалять ячейки с ленты.) После того, как все символы исчезли, мы достигли конечной строки. $hq_{r+2}h$.

Тогда процедура решения проблемы слов также даст процедуру определения того, завершается ли данная машина Тьюринга при запуске в определенном общем состоянии. $t$, проверяя, является ли $t$ и $hq_{r+2}h$ принадлежат к одному и тому же классу конгруэнтности относительно этой системы перезаписи строк. Технически имеем следующее:

Лемма. Позволять $M$ быть детерминированной машиной Тьюринга и $R$ быть системой перезаписи строк, реализующей $M$, как описано выше. Затем $M$ остановится при запуске из общего состояния, закодированного как $t$ тогда и только тогда, когда $t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h$ (то есть, тогда и только тогда, когда $t$ и $hq_{r+2}h$ конгруэнтны ли Туэ для $R$).

Что $t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h$ если $M$ останавливается при запуске с $t$ сразу после строительства $R$ (просто бег $M$ пока он не остановится, строит доказательство $t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h$), но ${\overset {*}{\underset {R}{\leftrightarrow }}}$ также позволяет машине Тьюринга $M$ сделать шаги назад. Здесь становится актуальным то, что $M$ является детерминированным, потому что тогда все шаги вперед уникальны; в ${\overset {*}{\underset {R}{\leftrightarrow }}}$ идти от $t$ к $hq_{r+2}h$ за последним шагом назад должен следовать его аналог в качестве шага вперед, поэтому эти два шага компенсируются, и с помощью индукции все шаги назад могут быть исключены из такого обхода. Следовательно, если $M$ не останавливается при запуске с $t$, т. е. если у нет нас $t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h$, то у нас нет тоже $t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h$. Поэтому, решив ${\overset {*}{\underset {R}{\leftrightarrow }}}$ сообщает нам ответ на проблему остановки для $M$.

Очевидным ограничением этого аргумента является то, что для создания полугруппы $\Sigma ^{*}{\big /}{\overset {*}{\underset {R}{\leftrightarrow }}}$ с неразрешимой проблемой слов нужно сначала иметь конкретный пример машины Тьюринга $M$ для которого проблема остановки неразрешима, но все различные машины Тьюринга, фигурирующие в доказательстве неразрешимости общей проблемы остановки, имеют в качестве компонента гипотетическую машину Тьюринга, решающую проблему остановки, поэтому ни одна из этих машин не может существовать на самом деле; все, что доказывает, это то, что существует некоторая машина Тьюринга, для которой проблема решения неразрешима. Однако наличие некоторой машины Тьюринга с неразрешимой проблемой остановки означает, что проблема остановки для универсальной машины Тьюринга неразрешима (поскольку она может имитировать любую машину Тьюринга), и были построены конкретные примеры универсальных машин Тьюринга.

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

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

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

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

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

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

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

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

См. также

• L-система
• Алгоритм Маркова — вариант системы перезаписи строк.
• МУ головоломка

Ссылки

Монографии

• Рональд В. Бук и Фридрих Отто, Системы переписывания строк , Springer, 1993, ISBN   0-387-97965-4 .
• Маттиас Янцен, Переписывание слитных строк , Биркхойзер, 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 .

Ориентировочные документы

• Пост, Эмиль (1947). «Рекурсивная неразрешимость проблемы Туэ» . Журнал символической логики . 12 (1): 1–11. дои : 10.2307/2267170 . JSTOR   2267170 . S2CID   30320278 . Архивировано из оригинала 29 сентября 2019 г. Проверено 29 сентября 2019 г.