Изменения
→Примеры решений проблем соответсвия Поста
'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.
{{Определение
|definition=
}}
== Примеры решений проблем соответсвия соответствия Поста ==
=== Пример 1 ===
!<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> является решением этой проблемы соотвествий Поста.
=== Пример 2 ===
Иногда возникает ситуация, когда решений конкретной проблемы соотвествия соответствия Поста нет.
{|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>
