МПСП неразрешима.
|proof=
Выполним [[M-сводимость|m-сведение]] множества строк, на которых заданная машина пар из машины Тьюринга (МТ) <tex>M</tex> и строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП.
--------Назовём '''снимком''' состояния МТ строку вида <tex>c_1 c_2 \ldots c_k \#_p c_{k+1} \ldots c_t</tex>, где <tex>c_1 c_2 \ldots c_t</tex> — строка на ленте без учёта пробелов, <tex>p</tex> — текущее состояние автомата МТ, <tex>\#_p</tex> соответствует положению головки. Построим последовательности таким образом, чтобы решение МПСП образовывало строку
Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> \$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{- недопуск. <tex>MT: (m, 2}} \$ \ldots \$ \#_{yes} \omega)</tex>. Задача <tex>m($ \omega) = Y$</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.
где <tex>a_1 = \$ \#_s \omega \$snap_i</tex>— снимки последовательных состояний МТ от стартового до конечного, <tex>b_1 = \$snap_{n_{-t}}</tex>— последний снимок с <tex>t</tex> удалёнными символами строки.Таким образом выводятся следующие последовательности: Оговоримся, что состояния <tex>\$ A_0 \$ \ldots \$ A_k \$no</tex> и в автомате МТ не существует (его роль может выполнять сток), допуск происходит при попадании в состояние <tex>\$ A_i \ldotsyes</tex> - мгновенное описание.
Если Сформируем последовательности <tex>MTa</tex> и <tex>b</tex> по МТ <tex>M</tex> и строке <tex>w</tex> остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.
<tex>a_1 = \forall c $ \in #_{start} w \Pi$ </tex> построим следующую пару , <tex>(a_i=c, b_i = c), (a_i = \$, b b_1 = \$)</tex>.<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.;
Соответственно для всех символов <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\deltaалфавита ленты (q, cза исключением пробела) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.Аналогично следует поступить и с переходом на месте, или считаем, что такого не бывает.:
Как может быть устроен префикс решения '''МПСП''':<tex>a_i = c</tex>, <tex>b_i = c</tex>,
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex>а также
<tex>ba_i = \$</tex>: , <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ b_i = \$ |</tex>;
Требуется добиться остановкидля всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \leftarrow \rangle</tex>: <tex>a_i = \#_q d</tex>, <tex>b_i = c \#_p</tex>; для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \rightarrow \rangle</tex>: <tex>a_i = d \#_q</tex>, <tex>b_i = \#_p c</tex>; для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \downarrow \rangle</tex>: <tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex>. Такие последовательности позволяют сформировать строки <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex> (из <tex>a</tex>) и <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex> (из <tex>b</tex>), но решения МПСП быть не может, так как все члены последовательностей, кроме первого, имеют равную длину, и строка, составленная из элементов <tex>a</tex>, всегда оказывается длиннее. Задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавляется далеедобавим в уже имеющиеся последовательности следующие элементы:* для всех символов <tex>c</tex>a алфавита ленты (за исключением пробела): <tex>a_i = \#_y_{yes}</tex>, <tex>b b_i = \#_y _{yes} c</tex>, * или <tex>a a_i = \#_y_{yes}</tex>, <tex>b b_i = c \#_y_{yes}</tex>, а также * или <tex>a a_i = \$ \$</tex>, <tex>b b_i = <tex> \#_{yes} \$ \$</tex>. С помощью новых элементов можно привести обе строки к виду <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_y _{yes} \$ \$</tex>, но только тогда, когда в <tex>snap_n</tex> содержится <tex>\#_{yes}</tex>; другими словами, только тогда, когда автомат, принадлежащий <tex>M</tex>, допускает <tex>w</tex>. Таким образом, выполнено успешное m-сведение множества пар из машины Тьюринга (МТ) <tex>M</tex> и строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП.
--------
}}
