171
правка
Изменения
м
Нет описания правки
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
|proof=
Пусть даны последовательности <tex>a_na, b_nb</tex> из условия ПСП. Количество последовательностей индексов, каждый из которых находится в пределах от 1 до <tex>n</tex>, длины <tex>m</tex> равно <tex>n^m</tex>. Программа-полуразрешитель <tex>p</tex> устроена следующим образом:
for <tex>m = 1 .. \infty</tex>
for all <tex>(i_1, i_2, \ldots, i_m): 1 \leq i_j \leq n</tex>
Выполним [[M-сводимость|m-сведение]] множества решений МПСП к множеству решений ПСП.
Пусть даны последовательности <tex>a_na, b_nb</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 \$</tex>, <tex>b'_{i+1} = \$ b_i</tex>;
