Изменения

Дана упорядоченная пара конечных последовательностей <tex>((a_1, \ldots, a_n), (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, называется '''проблемой соответствий Поста (ПСП)''' Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.

Язык пар последовательностей, для которых существует решение ПСП положительно, перечислим.

Для МПСП доказательство перечислимости имеющих положительное решение пар аналогично, но перебор индексов ведётся с <tex>i_2</tex>. {{Теорема|statement=МПСП неразрешима.|proof=Выполним [[M-сводимость|m-сведение]] множества строк, на которых заданная машина Тьюринга (МТ) не зависает, к множеству решений МПСП. --------

'''Известно''':{{Теорема* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''|statement=* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''неразрешима.'''Необходимо''':|proof=* Не существует решения '''Выполним [[M-сводимость|m-сведение]] множества решений МПСП''' <tex>\Rightarrow</tex> не существует решения '''к множеству решений ПСП'''.

Возьмём экземпляр задачи Пусть даны последовательности <tex>a_n, b_n</tex> из условия МПСП. Построим две новые последовательности <tex>a'_{n+2}, b'_{n+2}</tex>: * <tex>(( a'_1 = \$ a_1 \$</tex>, <tex>b'_1 = \$ b_1</tex>;* <tex>\forall i = 1 .. n</tex>: <tex>a'_{i+1} = a_i \ldots $</tex>, a_n ) <tex>b'_{i+1} = \$ b_i</tex>;* <tex>a'_{n+2} = \#</tex>, ( b_1 <tex>b'_{n+2} = \$ \#</tex>, где <tex>\ldots , b_n ))$</tex>. Вставим между каждой парой символов во всех строках символ , <tex>*\#</tex>— символы, не встречающиеся в словах исходных последовательностей.

<tex>i = 1</tex>{{Утверждение* <tex>a_1 |statement= * c_1 * c_2 \ldots c_l *</tex>* Существование решения МПСП для <tex>b_1 = * c_1 * c_2 \ldots c_la, b</tex>эквивалентно существованию решения ПСП для <tex>i = 2 \ldots n a', b'</tex>:.* <tex>a_i |proof= c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex>* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><tex>i = n + 1</tex>* <tex>a_{n+1} = \$</tex>* <tex>b_{n+1} = *\$Rightarrow</tex>

Теперь необходимо начать с Пусть <tex>(a_1a_{i_2} \ldots a_{i_k} = b_1 b_{i_2} \ldots b_{i_k}</tex>. Тогда <tex>a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = \$ a_1 \$ a_{i_2} \$ \ldots \$ a_{i_k} \$ \#</tex>, <tex>b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2} = \$ b_1)\$ b_{i_2} \$ \ldots \$ b_{i_k} \$ \#</tex>, т.к. все остальные пары начинаются с различных символовследовательно, <tex>a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2}</tex>.

Возникающее однозначное соответствие может быть решением этой системы <tex>\Leftarrow</tex> В любом существующем решении ПСП для <tex>a', b'</tex> должны выполняться условия: * <tex>i_1 = 1</tex>, так как только в паре <tex>(a'_1, b'_1)</tex> первые символы совпадают;* последний индекс равен <tex>n+2</tex>, так как только в паре <tex>(a'_{n+2}, b'_{n+2})</tex> строки заканчиваются одинаковыми символами. Пусть <tex>a'_1 a'_{i_2} \ldots a'_{i_k} = b'_1 b'_{i_2} \ldots b'_{i_k}</tex>. Если <tex>i_f</tex> — наименьший индекс, равный <tex>n+2</tex>, то <tex>a'_1 a'_{i_2} \ldots a'_{i_f}</tex>, <tex>b'_1 b'_{i_2} \ldots b'_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\#</tex>, следовательно, равны между собой. <tex>i_1, \ldots, i_f</tex> — также решение ПСП, причём <tex>i_1 = 1</tex>, <tex>i_f = n + 2</tex>. Остальные индексы не превосходят <tex>n+1</tex>, но и решением исходной задачине равны <tex>1</tex>, иначе в которой всё начиналось с пары левой части равенства образуется подстрока из двух <tex>(\$</tex> подряд, а в правой её не будет. Учитывая эти ограничения, перепишем получившееся равенство: <tex>\$ a_1\$ a_{i_2-1} \$ \ldots \$ a_{i_{f-1}-1} \$ \# = \$ b_1 \$ b_{i_2-1} \$ \ldots \$ b_{i_{f-1}-1} \$ \#</tex>, а значит, <tex>a_1 a_{i_2-1} \ldots a_{i_{f-1}-1} = b_1)b_{i_2-1} \ldots b_{i_{f-1}-1}</tex>.}} По доказанному ранее, МПСП неразрешима. Тогда, вследствие теоремы для m-сведения, ПСП неразрешима.}}