29
правок
Изменения
м
-/—
'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') - — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.
== Основные определения ==
<tex>\Rightarrow</tex>
Пусть набор индексов <tex>(1, i_2, \dots, i_k)</tex> - — решение МПСП из условия леммы. То есть <tex>w_A = w_B</tex>, где
<tex>w_A = a_1 a_{i_2} \dots a_{i_k}</tex>,
<tex>w_B = b_1 b_{i_2} \dots b_{i_k}</tex>.
Рассмотрев цепочки <tex>w_C</tex> и <tex>w_D</tex> c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа <tex>\#</tex> в начале, а второй - — в конце. Конкретно,
<tex>\# c_1 c_{i_2} \dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \# </tex>.
<tex> c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1} </tex>.
Итого, если <tex>(1, i_2, \dots, i_k)</tex> - — решение исходной МПСП, то <tex>(0, i_2, \dots, i_k, n+1)</tex> - — решение построенной по правилам выше ПСП.
<tex>\Leftarrow</tex>
ПСП не разрешима.
|proof=
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП - — неразрешима.
}}
