Изменения

Теперь покажем как свести универсальный язык к МПСП.{{Определение|definition=Назовём '''снимком''' состояния МТ строку вида <tex>c_1 c_2 \ldots c_k \#_p c_{k+1} \ldots c_t</tex>, где <tex>snap_ic_1 c_2 \ldots c_t</tex> — снимки последовательных состояний МТ от стартового до конечногострока на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>snap_{n_{-t}}p</tex> — последний снимок с текущее состояние автомата МТ, головка расположена справа от <tex>t\#_p</tex> удалёнными символами. Оговоримся, что состояния }}Построим списки <tex>noA</tex> в автомате МТ не существует (его роль может выполнять сток), допуск происходит при попадании в состояние и <tex>yesB</tex>.таким образом, чтобы решение МПСП образовывало строку

Сформируем последовательности <tex>a\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$</tex> и <tex>b</tex> по МТ <tex>M</tex> и строке <tex>w</tex>.,

где <tex>a_1 = \$' \#_snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{start-t} w }</tex> — последний снимок с <tex>t</tex> удалёнными символами, а <tex>\$ </tex>- символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния <tex>b_1 = \$'no</tex> в автомате МТ не существует, а допуск происходит при попадании в состояние <tex>yes</tex>;.

для всех символов Сформируем списки <tex>cA</tex> алфавита лентыи <tex>B</tex> по МТ <tex>M</tex> и входной строке <tex>w</tex>. Будем добавлять пары цепочек в эти списки по следующим правилам:

:1. <tex>a_1 = \$ \#_{start} w \$ </tex>, <tex>b_1 = \$</tex>. По определению МПСП эта пара всегда будет первой в любом решении.:2. <tex>a_i = c</tex>, <tex>b_i = c</tex>для всех символов <tex>c</tex> алфавита ленты.:3. <tex>a_i = \$</tex>, <tex>b_i = \$</tex>.:4. <tex>a_i = \#_q e d</tex>, <tex>b_i = e \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p,c) = \langle q, d, \leftarrow \rangle</tex> и для всех символов алфавита <tex>e</tex>.:5. <tex>a_i = d \#_q</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \rightarrow \rangle</tex>.:6. <tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \downarrow \rangle</tex>.

Заметим, что все элементы <tex>A</tex> и <tex>B</tex>, кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов <tex>A</tex>, всегда оказывается длиннее. Если представить процесс формирования решения МПСП как динамический, то строка из элементов <tex>B</tex> вынуждена постоянно "догонять" первую. Более того, можно заметить, что вторая строка всегда будет отставать ровно на один снимок. Действительно, первая пара из списков <tex>A</tex> и <tex>B</tex> задает это отставание. Затем при помощи элементов из правил <tex>4</tex>, <tex>5</tex> и <tex>6</tex> мы имитируем переход машины Тьюринга, добавляя во вторую строку то состояние и положение головки, которые были до перехода, а такжев первую строку - то состояние, положение головки и новый ленточный символ, которые стали после перехода. Нетрудно заметить, что тем самым строка составленная из элементов списка <tex>B</tex> будет соответствовать строке из элементов списка <tex>A</tex>, но с отставанием на один переход. Далее с помощью элементов из правил <tex>2</tex> и <tex>3</tex> мы допишем в обе строки одинаковые суффиксы текущего снимка, разделитель <tex>\$</tex> и префикс нового снимка до следующего перехода машины Тьюринга. Таким образом если первая строка равна

<tex>a_i = \$</tex>, <tex>b_i = \$</tex>; для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \leftarrow \rangle</tex> и для всех символов алфавита <tex>e</tex>: <tex>a_i = \#_q e d</tex>, <tex>b_i = e \#_p c</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>a</tex> и <tex>b</tex>, кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов <tex>a</tex>, всегда оказывается длиннее. Если представить процесс формирования решения МПСП как динамический, вторая строка вынуждена постоянно «догонять» первую. Более того, можно доказать по индукции, что если первая строка имеет вид <tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex>,

<tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex>,

<tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n+1} \$</tex>

<tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$ snap_n \$</tex>,

Задача Теперь стоит новая задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности следующие элементыпо следующим правилам:

:7. <tex>a_i = \#_{yes}</tex>, <tex>b_i = \#_{yes} c</tex>, для всех символов <tex>c</tex> алфавита ленты.:8. <tex>a_i = \#_{yes}</tex>, <tex>b_i = c \#_{yes}</tex>, для всех символов <tex>c</tex> алфавита ленты.:9. <tex>a_i = \$'</tex>, <tex>b_i = \#_{yes} \$ \$'</tex>.

Если состояние <tex>a_i = \#_{yes}</tex>недостижимо, в первой строке никогда не будет символа <tex>b_i = \#_{yes} c</tex>,и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину.

Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил <tex>a_i = \#_{yes}7</tex>, и <tex>8</tex> и копируя все остальные с помощью элементов из правил <tex>2</tex> и <tex>b_i = c \#_{yes}3</tex>,можно будет привести строки к виду

<tex>a_i = \$'</tex>, <tex>b_i = \#_{yes} \$ \$'</tex>. Если состояние <tex>yes</tex> недостижимо, в первой строке никогда не будет символа <tex>\#_{yes}</tex>, и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину. Если же допускающее состояние встретится, с помощью новых элементов можно будет привести обе строки к виду

<tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$'</tex>.

Другими словамиИ наконец, «сравнять» строки возможно тогда и только тогда, когда автомат, принадлежащий <tex>M</tex>, допускает <tex>w</tex>. Таким образом, выполнено успешное m-сведение множества пар с помощью элементов из машины Тьюринга (МТ) правила <tex>M9</tex> и сравняем строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП. }}

Последовательности Списки <tex>A</tex> и <tex>B</tex> для строки <tex>ab</tex> будут сформированы следующим образом:

! Последовательность aСписок A ! Последовательность bСписок B

|<tex>\$' \#_{start} ab \$</tex> |<tex>\$'</tex>

|<tex>\$' \#_{start} ab \$</tex> |<tex>\$'</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start}</tex> |<tex>\$' \#_{start} a</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b</tex> |<tex>\$' \#_{start} ab</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$</tex> |<tex>\$' \#_{start} ab \$</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b</tex> |<tex>\$' \#_{start} ab \$ b</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>

По доказанному ранее<tex>\Leftarrow</tex> Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, и, как было сказано выше, если в первой строке никогда не будет символа <tex>\#_{yes}</tex>, то "сравнять" строки по длине не удастся. Значит, если МПСП неразрешимаимеет решение, то символ <tex>\#_{yes}</tex> рано или поздно появится. ТогдаА значит и машина Тьюринга допустит <tex>w</tex>. }} {{Теорема|statement=ПСП не разрешима.|proof=Скомбинировав обе леммы, вследствие теоремы для m-сведениямы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП - неразрешима.