Изменения

Дана упорядоченная пара Даны два конечных последовательностей списка <tex>(A = (a_1, \ldots, a_n), </tex> и <tex>B = (b_1 ,\ldots ,b_n))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>(i_1 , \ldots, i_k)</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex>1 \leq i_j \leq n</tex> для каждого всех j, называется '''проблемой соответствий Поста (ПСП)'''(англ. ''Post correspondence problem''). Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.

Пусть даны последовательности Для списков <tex>aA</tex> и <tex>bB</tex> размера <tex>n</tex> из условия ПСП. Построим построим программу-полуразрешитель <tex>p</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 \ldots 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 \ldots 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=Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП. <tex>\Rightarrow</tex> Пусть набор индексов <tex>(1, i_2, \ldots, i_k)</tex> - решение МПСП из условия леммы. То есть <tex>w_A = w_B</tex>, где  <tex>w_A = a_1 a_{i_2} \ldots a_{i_k}</tex>, <tex>w_B = b_1 b_{i_2} \ldots b_{i_k}</tex>. Рассмотрев цепочки <tex>w_C</tex> и <tex>w_D</tex> c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа <tex>\#</tex> в начале, а второй - в конце. Конкретно, <tex>\# c_1 c_{i_2} \ldots c_{i_k} = d_1 d_{i_2} \ldots d_{i_k} \# </tex>. Изменив первый индекс с <tex>1</tex> на <tex>0</tex>, решим проблему с символом <tex>\#</tex> в начале. Добавив индекс <tex>n+1</tex> к набору, решим проблему с символом <tex>\#</tex> в конце. <tex> c_0 c_{i_2} \ldots c_{i_k} c_{n+1} = d_1 d_{i_2} \ldots d_{i_k} d_{n+1} </tex>. Итого, если <tex>(1, i_2, \ldots, i_k)</tex> - решение исходной МПСП, то <tex>(0, i_2, \ldots, i_k, n+1)</tex> - решение построенной по правилам выше ПСП. <tex>\Leftarrow</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> строки заканчиваются одинаковыми символами. Пусть последовательность <tex>(0, i_2, i_3, \ldots, i_k, n + 1)</tex> является решением ПСП. Иными словами, <tex>c_0 c_{i_2} \ldots c_{i_k} c_{n+1} = d_0 d_{i_2} \ldots d_{i_k} d_{n+1}</tex>. Если <tex>i_f</tex> — наименьший индекс, равный <tex>n+1</tex>, то <tex>c_0 c_{i_2} \ldots c_{i_f}</tex>, <tex>d_0 d_{i_2} \ldots d_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\$</tex>, следовательно, равны между собой. Последовательность <tex>(0, i_{2} \ldots, i_f)</tex> — также решение ПСП, причём первый индекс равен <tex>0</tex> и <tex>i_f = n + 1</tex>. Остальные индексы не превосходят <tex>n</tex>, но и не равны <tex>0</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\#</tex> подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство: <tex>\# c_1 c_{i_2} \ldots c_{i_{f-1}}\$</tex> <tex>=</tex> <tex>d_1 d_{i_2} \ldots d_{i_{f-1}} \#\$</tex>. Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>\$</tex>, получим <tex>a_1 a_{i_2} \ldots a_{i_{f-1}} = b_1 b_{i_2} \ldots b_{i_{f-1}}</tex>. Итого, если <tex>(0, i_2, \ldots, i_k, n+1)</tex> - решение ПСП, то <tex>(1, i_2, \ldots, i_k)</tex> - решение исходной МПСП.}} {{Лемма

Универсальный язык сводится к МПСП неразрешима.

Выполним [[M-сводимость|m-сведение]] множества пар из машины Тьюринга [[Разрешимые (МТрекурсивные) языки#Пример неразрешимого множества|универсального языка]] к МПСП со списками <tex>MA</tex> и строки <tex>wB</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП.

== Литература Источники ==