Изменения

Дана упорядоченная пара Даны два конечных последовательностей списка <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 \leq leqslant i_j \leq leqslant n</tex> для каждого всех <tex>j</tex>, называется '''проблемой соответствий Поста (ПСП)'''. Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.

Докажем [[Разрешимые (рекурсивные) языки|неразрешимость]] языка ПСП следующим образом. Докажем, что универсальный язык [[M-сводимость|сводится]] к языку МПСП, который в свою очередь сводится к языку ПСП. При этом отметим, что для унарного алфавита ПСП разрешима. === Cведение МПСП к ПСП === Пусть даны списки <tex>A</tex> и <tex>B</tex> из условия МПСП. Построим два новых списка <tex>C</tex> и <tex>D</tex> и рассмотрим ПСП для них. Для этого введем два новых символа, которые не используются в словах из цепочек <tex>A</tex> и <tex>B</tex>. Пусть для определенности это будут символы <tex>\#</tex> и <tex>\$</tex>. Тогда сформируем два новых списка <tex>C, D</tex> по следующим правилам:* для всех <tex>i = 1 \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 \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>c_{n+1} = \$</tex>,* <tex>d_{Утверждениеn+1} = \#\$</tex>.  {{Лемма|id=lemma-

Язык пар последовательностейМПСП для пары списков <tex>(A, B)</tex> сводится к ПСП для которых существует решение ПСПпары списков <tex>(C, перечислимD)</tex>.

Пусть даны последовательности Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП. <tex>a\Rightarrow</tex> и  Пусть набор индексов <tex>b(1, i_2, \dots, i_k)</tex> размера — решение МПСП из условия леммы. То есть <tex>nw_A = w_B</tex> из условия ПСП. Построим программу-полуразрешитель , где  <tex>pw_A = a_1 a_{i_2} \dots a_{i_k}</tex>, проверяющую все возможные решения: for <tex>m w_B = 1 .. b_1 b_{i_2} \inftydots b_{i_k}</tex>. for all Рассмотрев цепочки <tex>w_C</tex> и <tex>w_D</tex>(i_1c аналогичными индексами, i_2заметим, \ldotsчто мы имеем почти равные цепочки с той лишь разницей, i_m): 1 что первой не хватает символа <tex>\leq i_j \leq n#</tex>в начале, а второй — в конце. Конкретно,  if <tex>a_\# c_1 c_{i_1i_2} \ldots a_dots c_{i_mi_k} = b_d_1 d_{i_1i_2} \ldots b_dots d_{i_mi_k}\# </tex>. return trueТаким образомИзменив первый индекс с <tex>1</tex> на <tex>0</tex>, язык пар последовательностейрешим проблему с символом <tex>\#</tex> в начале. Добавив индекс <tex>n+1</tex> к набору, для которых существует решение ПСП, полуразрешим, а значит, перечислимрешим проблему с символом <tex>\#</tex> в конце.}}

Для МПСП доказательство перечислимости имеющих решение пар аналогично, но перебор индексов ведётся с <tex>c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1} </tex>.

{{Теорема|statement=МПСП неразрешима.|proof=Выполним [[M-сводимость|m-сведение]] множества пар из машины Тьюринга (МТ) Итого, если <tex>M</tex> и строки <tex>w(1, i_2, \dots, i_k)</tex>— решение исходной МПСП, где то <tex>M(w0, i_2, \dots, i_k, n+1)</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>\#_pLeftarrow</tex> соответствует положению головки. Построим последовательности таким образом, чтобы решение МПСП образовывало строку

В любом существующем решении ПСП для списков <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_C, D</tex> должны выполняться условия: * <tex>i_1 = 0</tex>, так как только в паре <tex>(c_1, d_1)</tex> первые символы совпадают,* последний индекс равен <tex>n+1</tex>, так как только в паре <tex>(c_{n_{-n+1}} \$ snap_, d_{n_{-2n+1}} \$ \ldots \$ \#_{yes} \$ \$)</tex>,строки заканчиваются одинаковыми символами.

где Пусть последовательность <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного(0, i_2, i_3, \dots, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами строки. Оговоримсяi_k, что состояния <tex>no</tex> в автомате МТ не существует (его роль может выполнять стокn + 1), допуск происходит при попадании в состояние <tex>yes</tex>является решением ПСП.Иными словами,

Сформируем последовательности <tex>a</tex> и <tex>b</tex> по МТ <tex>M</tex> и строке <tex>wc_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1}</tex>.

Если <tex>a_1 = i_f</tex> — наименьший индекс, равный <tex>n+1</tex>, то <tex>c_0 c_{i_2} \$ dots c_{i_f}</tex>, <tex>d_0 d_{i_2} \#_dots d_{starti_f} w </tex> — префиксы исходных конкатенаций до первого символа <tex>\$ </tex>, следовательно, равны между собой. Последовательность <tex>(0, i_{2} \dots, i_f)</tex> — также решение ПСП, причём первый индекс равен <tex>0</tex> и <tex>b_1 i_f = n + 1</tex>. Остальные индексы не превосходят <tex>n</tex>, но и не равны <tex>0</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\$#</tex>;подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:

для всех символов <tex>c\# c_1 c_{i_2} \dots c_{i_{f-1}}\$</tex> алфавита ленты (за исключением пробела):<tex>=</tex> <tex>d_1 d_{i_2} \dots d_{i_{f-1}} \#\$</tex>.

<tex>a_i = c</tex>Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>b_i = c\$</tex>,получим

Итого, если <tex>a_i = (0, i_2, \$dots, i_k, n+1)</tex>— решение ПСП, то <tex>b_i = (1, i_2, \$dots, i_k)</tex>;— решение исходной МПСП.}}

для всех правил === Сведение универсального языка к МПСП ==={{Определение|definition=Назовём '''снимком состояния [[Машина Тьюринга|МТ]]''' строку вида <tex>Mc_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t</tex> вида , где <tex>c_1 c_2 \delta (dots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>p</tex> — текущее состояние автомата МТ, c) = головка расположена справа от <tex>\langle q, d#_p</tex>.}}Построим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \rightarrow $ \rangle$</tex>:,

где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами, а <tex>a_i = d \#_q$</tex> — символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния <tex>no</tex>в автомате МТ не существует, а допуск происходит при попадании в состояние <tex>b_i = \#_p cyes</tex>;.

для всех правил Сформируем списки <tex>A</tex> и <tex>B</tex> по МТ <tex>M</tex> вида и входной строке <tex>\delta (p, c) = \langle q, d, \downarrow \ranglew</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>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$B</tex> (вынуждена постоянно "догонять" первую. Более того, можно заметить, что вторая строка всегда будет отставать ровно на один снимок. Действительно, первая пара из списков <tex>aA</tex>) и <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$B</tex> (задает это отставание. Затем при помощи элементов из правил <tex>b4</tex>), но решения МПСП быть не может<tex>5</tex> и <tex>6</tex> мы имитируем переход машины Тьюринга, так как все члены последовательностейдобавляя во вторую строку то состояние и положение головки, кроме первогокоторые были до перехода, имеют равную длинуа в первую строку - то состояние, положение головки и новый ленточный символ, которые стали после перехода. Нетрудно заметить, что тем самым строка, составленная из элементов списка <tex>aB</tex>будет соответствовать строке из элементов списка <tex>A</tex>, но с отставанием на один переход. Далее с помощью элементов из правил <tex>2</tex> и <tex>3</tex> мы допишем в обе строки одинаковые суффиксы текущего снимка, всегда оказывается длиннееразделитель <tex>\$</tex> и префикс нового снимка до следующего перехода машины Тьюринга.Таким образом если первая строка равна

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

<tex>a_i = \#_$ snap_1 \$ snap_2 \$ \dots \$ snap_{yesn-1}</tex>, <tex>b_i = \#_{yes} c$</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> не зависает, к множеству решений МПСПдостижимо.Для этого добавим в уже имеющиеся последовательности элементы по следующим правилам:

: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>yes</tex> недостижимо, в первой строке никогда не будет символа <tex>\#_{yes}</tex>, и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину.

{{Теорема|statement=ПСП неразрешима.|proof=Выполним [[M-сводимость|m-сведение]] множества решений МПСП Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил <tex>7</tex> и <tex>8</tex> и копируя все остальные с помощью элементов из правил <tex>2</tex> и <tex>3</tex> можно будет привести строки к множеству решений ПСП.виду

Пусть даны последовательности <tex>a, b</tex> из условия МПСП. Обозначим как <tex>left(w, c)</tex> и <tex>right(w, c)</tex> строки, состоящие из символов <tex>w</tex>, разделённых <tex>c</tex>: <tex>left(w, c) = c w_1 c w_2 \ldots c w_k</tex>, <tex>right(w, c) = w_1 c w_2 c $ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots w_k c\$ \#_{yes} \$</tex>.

{{Утверждение|statement=Существование решения МПСП для <tex>a, b</tex> эквивалентно существованию решения ПСП для <tex>a', b'\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ </tex>.|proof=<tex>\Rightarrow</tex>

<tex>w_a = a_1 a_{i_2} \ldots a_{i_k}</tex>,== Пример ===

Пусть автомат МТ состоит из двух состояний <tex>w_b = b_1 b_{i_2} \ldots b_{i_k}start</tex> и <tex>yes</tex>,алфавит ленты содержит символы <tex>a</tex> и <tex>b</tex>. Переходы автомата устроены следующим образом:

<tex>w_a \delta (start, a) = w_b\langle start, b, \rightarrow \rangle</tex>. Рассмотрим;

<tex>w'_a = a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = \$ rightdelta (a_1start, b) = \$) right(a_{i_2}langle yes, \$) \ldots right(a_{i_k}b, \$) downarrow \#rangle</tex>,;

из <tex>w'_b = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2} = left(b_1, \$) left(b_{i_2}, \$) \ldots left(b_{i_k}, \$) \$ \#yes</tex>переходов нет.

На чётных позициях в Списки <tex>w'_aA</tex> и <tex>w'_bB</tex> стоят равные символы из для строки <tex>w_aab</tex> и <tex>w_b</tex>, а также <tex>\#</tex> (в конце); на нечётных — <tex>\$</tex>. Следовательно, <tex>w'_a = w'_b</tex>, то естьбудут сформированы следующим образом:

{|class="wikitable" style="text-align: center" |- ! Номер элемента ! <tex>A</tex> ! <tex>B</tex> |- |1 |<tex>\$ \#_{start} ab \$</tex> |<tex>\$</tex> |- |2 |<tex>a'_1 </tex> |<tex>a'</tex> |- |3 |<tex>b</tex> |<tex>b</tex> |- |4 |<tex>\$</tex> |<tex>\$</tex> |- |5 |<tex>b \#_{i_2+1start} </tex> |<tex>\ldots a'#_{i_k+1start} a'</tex> |- |6 |<tex>\#_{n+2yes} = b'_1 </tex> |<tex>\#_{start} b'</tex> |- |7 |<tex>\#_{yes}</tex> |<tex>a \#_{i_2+1yes} </tex> |- |8 |<tex>\ldots #_{yes}</tex> |<tex>b'\#_{yes}</tex> |- |9 |<tex>\#_{yes}</tex> |<tex>\#_{yes} a</tex> |- |10 |<tex>\#_{yes}</tex> |<tex>\#_{i_k+1yes} b</tex> |- |11 |<tex>\$'</tex> |<tex>\#_{n+2yes}\$ \$'</tex>. |}

В любом существующем решении ПСП для {|class="wikitable" |- ! Шаг ! Индекс элемента ! Первая строка ! Вторая строка |- |align="center" | 1 |align="center" | 1 |<tex>\$ \#_{start} ab \$</tex> |<tex>\$</tex> |- |align="center" | 2 |align="center" | 5 |<tex>\$ \#_{start} ab \$ b \#_{start}</tex> |<tex>\$ \#_{start} a', </tex> |- |align="center" | 3 |align="center" | 3 |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex> |<tex>\$ \#_{start} ab</tex> |- |align="center" | 4 |align="center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$</tex> |<tex>\$ \#_{start} ab \$</tex> |- |align="center" | 5 |align="center" | 3 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b</tex> |<tex>\$ \#_{start} ab \$ b</tex> |- |align="center" | 6 |align="center" | 6 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex> |- |align="center" | 7 |align="center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b \$</tex> |- |align="center" | 8 |align="center" | 8 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex> |- |align="center" | 9 |align="center" | 3 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex> |- |align="center" | 10 |align="center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b'\$</tex> должны выполняться условия: * |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>i_1 |- |align="center" | 11 |align= 1"center" | 10 |<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>, так как только в паре |- |align="center" | 12 |align="center" | 4 |<tex>(a'_1, \$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b'_1)\$ \#_{yes} \$</tex> первые символы совпадают;* последний индекс равен |<tex>n+2\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex>, так как только в паре |- |align="center" | 13 |align="center" | 11 |<tex>(a\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex> |<tex>\$ \#_{n+2start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes}, b'\$ \#_{n+2yes})\$ \$'</tex> строки заканчиваются одинаковыми символами. |}

<tex>a'_1 a'_{i_2} \ldots a'_{i_k} = b'_1 b'_{i_2} \ldots b'_{i_k}Rightarrow</tex>.

Если <tex>i_fw</tex> — наименьший индекс, равный допускается <tex>n+2M</tex>, то можно проимитировать работу <tex>a'_1 a'_{i_2} \ldots a'_{i_f}M</tex>, со входом <tex>b'_1 b'_{i_2} \ldots b'_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\#w</tex>и, следовательнокак показано в примере выше, равны между собой. <tex>i_1, \ldots, i_f</tex> — также решение ПСП, причём получить равные строки из элементов списков <tex>i_1 = 1A</tex>, и <tex>i_f = n + 2B</tex>. Остальные индексы не превосходят <tex>n+1</tex>, но и не равны <tex>1</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\$</tex> подряд, а в правой её не может бытьТо есть найти решение МПСП. Учитывая эти ограничения, перепишем получившееся равенство:

<tex>\$ right(a_1, \$) right(a_{i_2-1}, \$) \ldots right(a_{i_{f-1}-1}, \$) \#Leftarrow</tex> <tex>=</tex> <tex>left(b_1, \$) left(b_{i_2-1}, \$) \ldots left(b_{i_{f-1}-1}, \$) \$ \#</tex>.

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

По доказанному ранее{{Теорема|statement=ПСП не разрешима.|proof=Скомбинировав обе леммы, МПСП неразрешима. Тогдамы сведем универсальный язык к языку ПСП, вследствие теоремы для m-сведенияа так как универсальный язык неразрешим, то и ПСП — неразрешима.

== Литература См. также ==* [[Неразрешимость исчисления предикатов первого порядка]]* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* [[Неразрешимость задачи об эквивалентности КС-грамматик]]* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]] == Источники информации ==* Джон ХопкрофтД., Раджив МотваниР., Джеффри УльманД. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0* [http://en.wikipedia.org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]