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