171
правка
Изменения
м
Нет описания правки
Назовём '''снимком''' состояния МТ строку вида <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>\$ ' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$'</tex>,
где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами. Оговоримся, что состояния <tex>no</tex> в автомате МТ не существует (его роль может выполнять сток), допуск происходит при попадании в состояние <tex>yes</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>\$ ' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$'</tex>.
Другими словами, «сравнять» строки возможно тогда и только тогда, когда автомат, принадлежащий <tex>M</tex>, допускает <tex>w</tex>. Таким образом, выполнено успешное m-сведение множества пар из машины Тьюринга (МТ) <tex>M</tex> и строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП.
