29
правок
Изменения
м
ldots -> dots
{{Определение
|definition=
Даны два конечных списка <tex>A = (a_1, \ldotsdots, a_n)</tex> и <tex>B = (b_1 ,\ldots dots ,b_n)</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>(i_1 , \ldotsdots, i_k)</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots dots a_{i_k} = b_{i_1} \ldots dots b_{i_k}</tex>, где <tex>1 \leqslant i_j \leqslant n</tex> для всех j, называется '''проблемой соответствий Поста (ПСП)'''. Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.
}}
Для списков <tex>A</tex> и <tex>B</tex> размера <tex>n</tex> из условия ПСП построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
for <tex>m = 1 .. \infty</tex>
for all <tex>(i_1, i_2, \ldotsdots, i_m): 1 \leqslant i_j \leqslant n</tex> if <tex>a_{i_1} \ldots dots a_{i_m} = b_{i_1} \ldots dots b_{i_m}</tex>
return true
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
Тогда сформируем два новых списка <tex>C, D</tex> по следующим правилам:
* Для всех <tex>i = 1 \ldots dots n</tex> возьмем <tex>c_i</tex> равное слову <tex>a_i</tex> с символом <tex>\#</tex> после каждого его символа. Например, для <tex>a_i = 10zx</tex> положим <tex>c_i = 1\#0\#z\#x\#</tex>;* Для всех <tex>i = 1 \ldots dots n</tex> возьмем <tex>d_i</tex> равное слову <tex>b_i</tex> с символом <tex>\#</tex> перед каждым его символом. Например, для <tex>b_i = 10zx</tex> положим <tex>d_i = \#1\#0\#z\#x</tex>;
* <tex>c_0 = \#c_1</tex>;
* <tex>d_0 = d_1</tex>;
<tex>\Rightarrow</tex>
Пусть набор индексов <tex>(1, i_2, \ldotsdots, i_k)</tex> - решение МПСП из условия леммы. То есть <tex>w_A = w_B</tex>, где
<tex>w_A = a_1 a_{i_2} \ldots dots a_{i_k}</tex>,
<tex>w_B = b_1 b_{i_2} \ldots dots b_{i_k}</tex>.
Рассмотрев цепочки <tex>w_C</tex> и <tex>w_D</tex> c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа <tex>\#</tex> в начале, а второй - в конце. Конкретно,
<tex>\# c_1 c_{i_2} \ldots dots c_{i_k} = d_1 d_{i_2} \ldots dots d_{i_k} \# </tex>.
Изменив первый индекс с <tex>1</tex> на <tex>0</tex>, решим проблему с символом <tex>\#</tex> в начале. Добавив индекс <tex>n+1</tex> к набору, решим проблему с символом <tex>\#</tex> в конце.
<tex> c_0 c_{i_2} \ldots dots c_{i_k} c_{n+1} = d_0 d_{i_2} \ldots dots d_{i_k} d_{n+1} </tex>.
Итого, если <tex>(1, i_2, \ldotsdots, i_k)</tex> - решение исходной МПСП, то <tex>(0, i_2, \ldotsdots, i_k, n+1)</tex> - решение построенной по правилам выше ПСП.
<tex>\Leftarrow</tex>
* последний индекс равен <tex>n+1</tex>, так как только в паре <tex>(c_{n+1}, d_{n+1})</tex> строки заканчиваются одинаковыми символами.
Пусть последовательность <tex>(0, i_2, i_3, \ldotsdots, i_k, n + 1)</tex> является решением ПСП. Иными словами,
<tex>c_0 c_{i_2} \ldots dots c_{i_k} c_{n+1} = d_0 d_{i_2} \ldots dots d_{i_k} d_{n+1}</tex>.
Если <tex>i_f</tex> — наименьший индекс, равный <tex>n+1</tex>, то <tex>c_0 c_{i_2} \ldots dots c_{i_f}</tex>, <tex>d_0 d_{i_2} \ldots dots d_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\$</tex>, следовательно, равны между собой. Последовательность <tex>(0, i_{2} \ldotsdots, i_f)</tex> — также решение ПСП, причём первый индекс равен <tex>0</tex> и <tex>i_f = n + 1</tex>. Остальные индексы не превосходят <tex>n</tex>, но и не равны <tex>0</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\#</tex> подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:
<tex>\# c_1 c_{i_2} \ldots dots c_{i_{f-1}}\$</tex> <tex>=</tex> <tex>d_1 d_{i_2} \ldots dots d_{i_{f-1}} \#\$</tex>.
Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>\$</tex>, получим
<tex>a_1 a_{i_2} \ldots dots a_{i_{f-1}} = b_1 b_{i_2} \ldots dots b_{i_{f-1}}</tex>.
Итого, если <tex>(0, i_2, \ldotsdots, i_k, n+1)</tex> - решение ПСП, то <tex>(1, i_2, \ldotsdots, i_k)</tex> - решение исходной МПСП.
}}
{{Определение
|definition=
Назовём '''снимком''' состояния МТ строку вида <tex>c_1 c_2 \ldots dots c_k \#_p c_{k+1} \ldots dots c_t</tex>, где <tex>c_1 c_2 \ldots dots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>p</tex> — текущее состояние автомата МТ, головка расположена справа от <tex>\#_p</tex>.
}}
Построим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку
<tex>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots dots \$ \#_{yes} \$ \$</tex>,
где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами, а <tex>\$</tex> - символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния <tex>no</tex> в автомате МТ не существует, а допуск происходит при попадании в состояние <tex>yes</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>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$</tex>,
то вторая будет равна
<tex>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_{n-1} \$</tex>,
а через несколько шагов они изменятся на
<tex>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n+1} \$</tex>
и
<tex>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_{n-1} \$ snap_n \$</tex>,
соответственно.
Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил <tex>7</tex> и <tex>8</tex> и копируя все остальные с помощью элементов из правил <tex>2</tex> и <tex>3</tex> можно будет привести строки к виду
<tex>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots dots \$ \#_{yes} \$</tex>
и
<tex>\$ snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots dots \$ </tex>.
И наконец, с помощью элементов из правила <tex>9</tex> сравняем строки.
