748
правок
Изменения
→Перечислимость языка ПСП
|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>
