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>
if <tex>a_{i_1} \ldots a_{i_m} = b_{i_1} \ldots b_{i_m}</tex>
return 1true
Таким образом, язык пар указанных последовательностей полуразрешим, а значит, перечислим.
}}
