Изменения
→Примеры решений проблем соответсвия Поста
'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.
{{Определение
|definition=
}}
== Примеры решений проблем соответствия Поста == === Пример 1 ==={{Определение|class="wikitable" style="text-align: center" |- !Номер элемента !<tex>1</tex> !<tex>2</tex> !<tex>3</tex> |- !<tex>A</tex> |<tex>01</tex> |<tex>1</tex> |<tex>011</tex> |- !<tex>B</tex> |<tex>101</tex> |<tex>11</tex> |<tex>01</tex> |definition=}Проблема Решение этой проблемы соответствий Постабудет являться последовательность индексов <tex>(3, 1, 3, для которой фиксирован элемент последовательности индексов 2)</tex>.Проверим это. <tex>i_1 sA = 011, 01, 011, 1</tex> <tex>sB = 01, 101, 01, 11</tex> Получаем то, называется '''модифицированной проблемой соответствий Поста что строки <tex>sA</tex> и <tex>sB</tex> равны, а значит последовательность индексов <tex>(МПСП3, 1, 3, 2)'''</tex> является решением этой проблемы соотвествий Поста. === Пример 2 ===Иногда возникает ситуация, когда решений конкретной проблемы соответствия Поста нет.{|class="wikitable" style="text-align: center" |- !Номер элемента !<tex>1</tex> !<tex>2</tex> !<tex>3</tex> |- !<tex>A</tex> |<tex>01</tex> |<tex>101</tex> |<tex>011</tex> |- !<tex>B</tex> |<tex>0</tex> |<tex>10</tex> |<tex>111</tex> |} Заметим, что если бы решение существовало оно должно было начинаться с индекса <tex>1</tex> или <tex>2</tex>.Но тогда строки получаемые из <tex>A</tex> всегда будут строго больше по длине, чем строки полученные из <tex>B</tex>, так как <tex> \mathrm{length}(A[i]) \geqslant \mathrm{length}(B[i])</tex> для всех <tex>i</tex>. Решения не существует. == Перечислимость языка ПСП ==
{{Теорема
|statement=
Язык пар последовательностей, для которых существует решение ПСП, [[Перечислимые языки | перечислим]].
|proof=
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
}}
{{ТеоремаОпределение|definition=Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов <tex>i_1 = 1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.}} Докажем [[Разрешимые (рекурсивные) языки|неразрешимость]] языка ПСП следующим образом. Докажем, что универсальный язык [[M-сводимость|сводится]] к языку МПСП, который в свою очередь сводится к языку ПСП. При этом отметим, что для унарного алфавита ПСП разрешима. === Cведение МПСП к ПСП === Пусть даны списки <tex>A</tex> и <tex>B</tex> из условия МПСП. Построим два новых списка <tex>C</tex> и <tex>D</tex> и рассмотрим ПСП для них. Для этого введем два новых символа, которые не используются в словах из цепочек <tex>A</tex> и <tex>B</tex>. Пусть для определенности это будут символы <tex>\#</tex> и <tex>\$</tex>. Тогда сформируем два новых списка <tex>C, D</tex> по следующим правилам:* для всех <tex>i = 1 \dots n</tex> возьмем <tex>c_i</tex> равное слову <tex>a_i</tex> с символом <tex>\#</tex> после каждого его символа. Например, для <tex>a_i = 10zx</tex> положим <tex>c_i = 1\#0\#z\#x\#</tex>,* для всех <tex>i = 1 \dots n</tex> возьмем <tex>d_i</tex> равное слову <tex>b_i</tex> с символом <tex>\#</tex> перед каждым его символом. Например, для <tex>b_i = 10zx</tex> положим <tex>d_i = \#1\#0\#z\#x</tex>,* <tex>c_0 = \#c_1</tex>,* <tex>d_0 = d_1</tex>,* <tex>c_{n+1} = \$</tex>,* <tex>d_{n+1} = \#\$</tex>. {{Лемма|id=lemma-
|statement=
МПСП неразрешимадля пары списков <tex>(A, B)</tex> сводится к ПСП для пары списков <tex>(C, D)</tex>.
|proof=
<tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_w_A = a_1 a_{n_{-2}i_2} \$ \ldots \$ \#_dots a_{yesi_k} \$ \$'</tex>,
<tex>a_1 = \$' \#_c_1 c_{starti_2} w \$ </tex>, <tex>b_1 dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \$'# </tex>;.
<tex>a_i c_0 c_{i_2} \dots c_{i_k} c_{n+1} = cd_0 d_{i_2} \dots d_{i_k} d_{n+1} </tex>, <tex>b_i = c</tex>,.
<tex>a_i = \$Leftarrow</tex>, <tex>b_i = \$</tex>;
В любом существующем решении ПСП для всех правил списков <tex>MC, D</tex> вида должны выполняться условия: * <tex>i_1 = 0</tex>, так как только в паре <tex>\delta (pc_1, cd_1) = \langle q</tex> первые символы совпадают, d, \leftarrow \rangle* последний индекс равен <tex>n+1</tex> и для всех символов алфавита , так как только в паре <tex>e(c_{n+1}, d_{n+1})</tex>:строки заканчиваются одинаковыми символами.
Пусть последовательность <tex>a_i = (0, i_2, i_3, \#_q e ddots, i_k, n + 1)</tex>является решением ПСП. Иными словами, <tex>b_i = e \#_p c</tex>;
Если <tex>a_i = d i_f</tex> — наименьший индекс, равный <tex>n+1</tex>, то <tex>c_0 c_{i_2} \dots c_{i_f}</tex>, <tex>d_0 d_{i_2} \dots d_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\$</tex>, следовательно, равны между собой. Последовательность <tex>(0, i_{2} \#_qdots, i_f)</tex>— также решение ПСП, причём первый индекс равен <tex>0</tex>b_i и <tex>i_f = n + 1</tex>. Остальные индексы не превосходят <tex>n</tex>, но и не равны <tex>0</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\#_p c</tex>;подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:
Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>a_i = \#_q d$</tex>, <tex>b_i = \#_p c</tex>.получим
Итого, если <tex>(0, i_2, \dots, i_k, n+1)</tex> — решение ПСП, то <tex>(1, i_2, \dots, i_k)</tex> — решение исходной МПСП.}} === Сведение универсального языка к МПСП ==={{Определение|definition=Назовём '''снимком состояния [[Машина Тьюринга|МТ]]''' строку вида <tex>c_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t</tex>, где <tex>c_1 c_2 \dots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>p</tex> — текущее состояние автомата МТ, головка расположена справа от <tex>\#_p</tex>.}}Построим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$ \$</tex>, где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами, а <tex>\$</tex> — символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния <tex>no</tex> в автомате МТ не существует, а допуск происходит при попадании в состояние <tex>yes</tex>. Сформируем списки <tex>A</tex> и <tex>B</tex> по МТ <tex>M</tex> и входной строке <tex>w</tex>. Будем добавлять пары цепочек в эти списки по следующим правилам: :1. <tex>a_1 = \$ \#_{start} w \$ </tex>, <tex>b_1 = \$</tex>. По определению МПСП эта пара всегда будет первой в любом решении.:2. <tex>a_i = c</tex>, <tex>b_i = c</tex> для всех символов <tex>c</tex> алфавита ленты.:3. <tex>a_i = \$</tex>, <tex>b_i = \$</tex>.:4. <tex>a_i = \#_q e d</tex>, <tex>b_i = e \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \leftarrow \rangle</tex> и для всех символов алфавита <tex>e</tex>.:5. <tex>a_i = d \#_q</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \rightarrow \rangle</tex>.:6. <tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \downarrow \rangle</tex>. Заметим, что все элементы <tex>A</tex> и <tex>B</tex>, кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов <tex>A</tex>, всегда оказывается длиннее. Если представить процесс формирования решения МПСП как динамический, то строка из элементов <tex>B</tex> вынуждена постоянно "догонять" первую. Более того, можно заметить, что вторая строка всегда будет отставать ровно на один снимок. Действительно, первая пара из списков <tex>A</tex> и <tex>B</tex> задает это отставание. Затем при помощи элементов из правил <tex>4</tex>, <tex>5</tex> и <tex>6</tex> мы имитируем переход машины Тьюринга, добавляя во вторую строку то состояние и положение головки, которые были до перехода, а в первую строку - то состояние, положение головки и новый ленточный символ, которые стали после перехода. Нетрудно заметить, что тем самым строка составленная из элементов списка <tex>B</tex> будет соответствовать строке из элементов списка <tex>A</tex>, но с отставанием на один переход. Далее с помощью элементов из правил <tex>2</tex> и <tex>3</tex> мы допишем в обе строки одинаковые суффиксы текущего снимка, разделитель <tex>\$</tex> и префикс нового снимка до следующего перехода машины Тьюринга. Таким образом если первая строка равна <tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$</tex>,
то вторая будет равна
<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_{n-1} \$</tex>,
а через несколько шагов они изменятся на
<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n+1} \$</tex>
и
<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_{n-1} \$ snap_n \$</tex>,
соответственно.
:7. <tex>a_i = \#_{yes}</tex>, <tex>b_i = \#_{yes} c</tex>, для всех символов <tex>c</tex> алфавита ленты.:8. <tex>a_i = \#_{yes}</tex>, <tex>b_i = c \#_{yes}</tex>, для всех символов <tex>c</tex> алфавита ленты.:9. <tex>a_i = \$'</tex>, <tex>b_i = \#_{yes} \$ \$'</tex>.
Если состояние <tex>a_i = \#_{yes}</tex>недостижимо, в первой строке никогда не будет символа <tex>b_i = \#_{yes} c</tex>,и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину.
Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил <tex>a_i = \#_{yes}7</tex>, и <tex>8</tex> и копируя все остальные с помощью элементов из правил <tex>2</tex> и <tex>b_i = c \#_{yes}3</tex>,можно будет привести строки к виду
<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots dots \$ \#_{yes} \$ \$'</tex>.
=== Пример ===
из <tex>yes</tex> переходов нет.
{|class="wikitable" style="text-align: center"
|-
! Номер элемента
! Последовательность a<tex>A</tex> ! Последовательность b<tex>B</tex>
|-
|1
|<tex>\$' \#_{start} ab \$</tex> |<tex>\$'</tex>
|-
|2
|align="center" | 1
|align="center" | 1
|<tex>\$' \#_{start} ab \$</tex> |<tex>\$'</tex>
|-
|align="center" | 2
|align="center" | 5
|<tex>\$' \#_{start} ab \$ b \#_{start}</tex> |<tex>\$' \#_{start} a</tex>
|-
|align="center" | 3
|align="center" | 3
|<tex>\$' \#_{start} ab \$ b \#_{start} b</tex> |<tex>\$' \#_{start} ab</tex>
|-
|align="center" | 4
|align="center" | 4
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$</tex> |<tex>\$' \#_{start} ab \$</tex>
|-
|align="center" | 5
|align="center" | 3
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b</tex> |<tex>\$' \#_{start} ab \$ b</tex>
|-
|align="center" | 6
|align="center" | 6
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b</tex>
|-
|align="center" | 7
|align="center" | 4
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$</tex>
|-
|align="center" | 8
|align="center" | 8
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex>
|-
|align="center" | 9
|align="center" | 3
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>
|-
|align="center" | 10
|align="center" | 4
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>
|-
|align="center" | 11
|align="center" | 10
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b</tex>
|-
|align="center" | 12
|align="center" | 4
|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex>
|-
|align="center" | 13
|align="center" | 11
|<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>
|}
{{ТеоремаЛемма
|statement=
|proof=
<tex>\Rightarrow</tex>
<tex>\Leftarrow</tex>
}}
== Литература Источники информации ==
* Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0
* [http://en.wikipedia.org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]