Изменения

Полуразрешимость: Возьмём возможно взять по возрастанию все возможные наборы индексов, применим применить конкатенацию и сравнимсравнить полученные строки. Сошлось - При совпадении задача будет решена, иначе - программа завислазависнет.

Сначала докажем приведём доказательства для случая, когда <tex>i_1 = 1</tex>, т.е. для '''МПСП'''. Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.

Получаем Таким образом выводятся следующие последовательности: <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, и <tex>\$ A_i \ldots</tex>- мгновенное описание.

Если <tex>MT</tex> остановится, добьёмся нужно добиться того, чтобы строка закончилосьзакончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.

<tex>\forall c \in \Pi</tex> заведём построим следующую пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.