Изменения
→Примеры решений проблем соответсвия Поста
'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.
{{Определение
|definition=
}}
== Примеры решений проблем соответсвия соответствия Поста ==<tex>=== Пример 1)</tex>===
{|class="wikitable" style="text-align: center"
|-
!<tex>2</tex>
!<tex>3</tex>
|-
!<tex>A</tex>
|<tex>01</tex>
|<tex>1</tex>
|<tex>101</tex> |<tex>11011</tex>
|-
!<tex>B</tex>
|<tex>0101</tex>
|<tex>11</tex>
|<tex>10</tex> |<tex>11101</tex>
|}
Решение этой проблемы соответствий Поста будет являться последовательность индексов <tex>(3, 1, 4, 3, 2)</tex>.
Проверим это.
<tex>sA = 011, 01, 11, 101011, 1</tex>
<tex>sB = 001, 111101, 1001, 11</tex>
Получаем то, что строки <tex>sA</tex> и <tex>sB</tex> равны, а значит последовательность индексов <tex>(3, 1, 4, 3, 2)</tex> является решением этой проблемы соотвествий Поста.
{|class="wikitable" style="text-align: center"
|-
|proof=
Для списков <tex>A</tex> и <tex>B</tex> размера <tex>n</tex> из условия ПСП построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
'''for''' <tex>m = 1 .. \dots \infty</tex>
'''foreach''' <tex>(i_1, i_2, \dots, i_m): 1 \leqslant i_j \leqslant n</tex>
'''if''' <tex>a_{i_1} \dots a_{i_m} = b_{i_1} \dots b_{i_m}</tex>
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
}}
== Неразрешимость языка ПСП ==
}}
Докажем [[Разрешимые (рекурсивные) языки|неразрешимость]] языка ПСП следующим образом. Докажем, что универсальный язык [[M-сводимость|сводится]] к языку МПСП, который в свою очередь сводится к языку ПСП. При этом отметим, что для унарного алфавита ПСП разрешима.
Пусть даны списки <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>.
В любом существующем решении ПСП для списков <tex>C, D</tex> должны выполняться условия:
* <tex>i_1 = 0</tex>, так как только в паре <tex>(c_1, d_1)</tex> первые символы совпадают;,
* последний индекс равен <tex>n+1</tex>, так как только в паре <tex>(c_{n+1}, d_{n+1})</tex> строки заканчиваются одинаковыми символами.
{{Определение
|definition=
<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>. Будем добавлять пары цепочек в эти списки по следующим правилам:
