171
правка
Изменения
м
Нет описания правки
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
|proof=
Пусть даны последовательности <tex>a</tex> и <tex>b</tex> размера <tex>n</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>
