Примеры неразрешимых задач: проблема соответствий Поста

Материал из Викиконспекты
Перейти к: навигация, поиск

Проблема соответствий Поста (англ. Post correspondence problem) — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.


Определение:
Даны два конечных списка [math]A = (a_1, \dots, a_n)[/math] и [math]B = (b_1 ,\dots ,b_n)[/math], где [math]a_i \in \Sigma ^*[/math] и [math]b_i \in \Sigma ^*[/math] для всех [math]i[/math]. Вопрос существования непустой последовательности индексов [math](i_1 , \dots, i_k)[/math], удовлетворяющей условию [math]a_{i_1} \dots a_{i_k} = b_{i_1} \dots b_{i_k}[/math], где [math]1 \leqslant i_j \leqslant n[/math] для всех [math]j[/math], называется проблемой соответствий Поста (ПСП). Такую последовательность индексов, в случае её существования, называют решением проблемы соответствий Поста.


Примеры решений проблем соответсвия Поста

[math]1)[/math]

Номер элемента [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math]
[math]A[/math] [math]01[/math] [math]1[/math] [math]101[/math] [math]11[/math]
[math]B[/math] [math]0[/math] [math]11[/math] [math]10[/math] [math]111[/math]

Решение этой проблемы соответствий Поста будет являться последовательность индексов [math](1, 4, 3, 2)[/math]. Проверим это.

[math]sA = 01, 11, 101, 1[/math]

[math]sB = 0, 111, 10, 11[/math]

Получаем то, что строки [math]sA[/math] и [math]sB[/math] равны, а значит последовательность индексов [math](1, 4, 3, 2)[/math] является решением этой проблемы соотвествий Поста.

[math]2)[/math] Иногда возникает ситуация, когда решений конкретной проблемы соотвествия Поста нет.

Номер элемента [math]1[/math] [math]2[/math] [math]3[/math]
[math]A[/math] [math]01[/math] [math]101[/math] [math]011[/math]
[math]B[/math] [math]0[/math] [math]10[/math] [math]111[/math]

Заметим, что если бы решение существовало оно должно было начинаться с индекса [math]1[/math] или [math]2[/math]. Но тогда строки получаемые из [math]A[/math] всегда будут строго больше по длине, чем строки полученные из [math]B[/math], так как [math] \mathrm{length}(A[i]) \geqslant \mathrm{length}(B[i])[/math] для всех [math]i[/math].

Решения не существует.

Перечислимость языка ПСП

Теорема:
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
Доказательство:
[math]\triangleright[/math]

Для списков [math]A[/math] и [math]B[/math] размера [math]n[/math] из условия ПСП построим программу-полуразрешитель [math]p[/math], проверяющую все возможные решения:

 for [math]m = 1 .. \infty[/math]
   foreach [math](i_1, i_2, \dots, i_m): 1 \leqslant i_j \leqslant n[/math]
     if [math]a_{i_1} \dots a_{i_m} = b_{i_1} \dots b_{i_m}[/math]
       return true
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
[math]\triangleleft[/math]

Для МПСП доказательство перечислимости имеющих решение пар аналогично, но перебор индексов ведётся с [math]i_2[/math].

Неразрешимость языка ПСП

Определение:
Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов [math]i_1 = 1[/math], называется модифицированной проблемой соответствий Поста (МПСП).


Докажем неразрешимость языка ПСП следующим образом. Докажем, что универсальный язык сводится к языку МПСП, который в свою очередь сводится к языку ПСП.

Для начала покажем как свести МПСП к ПСП.

Пусть даны списки [math]A[/math] и [math]B[/math] из условия МПСП. Построим два новых списка [math]C[/math] и [math]D[/math] и рассмотрим ПСП для них. Для этого введем два новых символа, которые не используются в словах из цепочек [math]A[/math] и [math]B[/math]. Пусть для определенности это будут символы [math]\#[/math] и [math]\$[/math].

Тогда сформируем два новых списка [math]C, D[/math] по следующим правилам:

  • Для всех [math]i = 1 \dots n[/math] возьмем [math]c_i[/math] равное слову [math]a_i[/math] с символом [math]\#[/math] после каждого его символа. Например, для [math]a_i = 10zx[/math] положим [math]c_i = 1\#0\#z\#x\#[/math];
  • Для всех [math]i = 1 \dots n[/math] возьмем [math]d_i[/math] равное слову [math]b_i[/math] с символом [math]\#[/math] перед каждым его символом. Например, для [math]b_i = 10zx[/math] положим [math]d_i = \#1\#0\#z\#x[/math];
  • [math]c_0 = \#c_1[/math];
  • [math]d_0 = d_1[/math];
  • [math]c_{n+1} = \$[/math];
  • [math]d_{n+1} = \#\$[/math].


Лемма:
МПСП для пары списков [math](A, B)[/math] сводится к ПСП для пары списков [math](C, D)[/math].
Доказательство:
[math]\triangleright[/math]

Из определения m-сведения следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП.

[math]\Rightarrow[/math]

Пусть набор индексов [math](1, i_2, \dots, i_k)[/math] — решение МПСП из условия леммы. То есть [math]w_A = w_B[/math], где

[math]w_A = a_1 a_{i_2} \dots a_{i_k}[/math],

[math]w_B = b_1 b_{i_2} \dots b_{i_k}[/math].

Рассмотрев цепочки [math]w_C[/math] и [math]w_D[/math] c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа [math]\#[/math] в начале, а второй — в конце. Конкретно,

[math]\# c_1 c_{i_2} \dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \# [/math].

Изменив первый индекс с [math]1[/math] на [math]0[/math], решим проблему с символом [math]\#[/math] в начале. Добавив индекс [math]n+1[/math] к набору, решим проблему с символом [math]\#[/math] в конце.

[math] c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1} [/math].

Итого, если [math](1, i_2, \dots, i_k)[/math] — решение исходной МПСП, то [math](0, i_2, \dots, i_k, n+1)[/math] — решение построенной по правилам выше ПСП.

[math]\Leftarrow[/math]

В любом существующем решении ПСП для списков [math]C, D[/math] должны выполняться условия:

  • [math]i_1 = 0[/math], так как только в паре [math](c_1, d_1)[/math] первые символы совпадают;
  • последний индекс равен [math]n+1[/math], так как только в паре [math](c_{n+1}, d_{n+1})[/math] строки заканчиваются одинаковыми символами.

Пусть последовательность [math](0, i_2, i_3, \dots, i_k, n + 1)[/math] является решением ПСП. Иными словами,

[math]c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1}[/math].

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

[math]\# c_1 c_{i_2} \dots c_{i_{f-1}}\$[/math] [math]=[/math] [math]d_1 d_{i_2} \dots d_{i_{f-1}} \#\$[/math].

Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца [math]\$[/math], получим

[math]a_1 a_{i_2} \dots a_{i_{f-1}} = b_1 b_{i_2} \dots b_{i_{f-1}}[/math].

Итого, если [math](0, i_2, \dots, i_k, n+1)[/math] — решение ПСП, то [math](1, i_2, \dots, i_k)[/math] — решение исходной МПСП.
[math]\triangleleft[/math]


Теперь покажем как свести универсальный язык к МПСП.

Определение:
Назовём снимком состояния МТ строку вида [math]c_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t[/math], где [math]c_1 c_2 \dots c_t[/math] — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, [math]p[/math] — текущее состояние автомата МТ, головка расположена справа от [math]\#_p[/math].

Построим списки [math]A[/math] и [math]B[/math] таким образом, чтобы решение МПСП образовывало строку

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$ \$[/math],

где [math]snap_i[/math] — снимки последовательных состояний МТ от стартового до конечного, [math]snap_{n_{-t}}[/math] — последний снимок с [math]t[/math] удалёнными символами, а [math]\$[/math] - символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния [math]no[/math] в автомате МТ не существует, а допуск происходит при попадании в состояние [math]yes[/math].

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

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

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

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$[/math],

то вторая будет равна

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$[/math],

а через несколько шагов они изменятся на

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n+1} \$[/math]

и

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$ snap_n \$[/math],

соответственно.

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

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

Если состояние [math]yes[/math] недостижимо, в первой строке никогда не будет символа [math]\#_{yes}[/math], и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину.

Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил [math]7[/math] и [math]8[/math] и копируя все остальные с помощью элементов из правил [math]2[/math] и [math]3[/math] можно будет привести строки к виду

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$[/math]

и

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ [/math].

И наконец, с помощью элементов из правила [math]9[/math] сравняем строки.

Пример

Пусть автомат МТ состоит из двух состояний [math]start[/math] и [math]yes[/math], алфавит ленты содержит символы [math]a[/math] и [math]b[/math]. Переходы автомата устроены следующим образом:

[math]\delta (start, a) = \langle start, b, \rightarrow \rangle[/math];

[math]\delta (start, b) = \langle yes, b, \downarrow \rangle[/math];

из [math]yes[/math] переходов нет.

Списки [math]A[/math] и [math]B[/math] для строки [math]ab[/math] будут сформированы следующим образом:

Номер элемента [math]A[/math] [math]B[/math]
1 [math]\$ \#_{start} ab \$[/math] [math]\$[/math]
2 [math]a[/math] [math]a[/math]
3 [math]b[/math] [math]b[/math]
4 [math]\$[/math] [math]\$[/math]
5 [math]b \#_{start}[/math] [math]\#_{start} a[/math]
6 [math]\#_{yes} b[/math] [math]\#_{start} b[/math]
7 [math]\#_{yes}[/math] [math]a \#_{yes}[/math]
8 [math]\#_{yes}[/math] [math]b \#_{yes}[/math]
9 [math]\#_{yes}[/math] [math]\#_{yes} a[/math]
10 [math]\#_{yes}[/math] [math]\#_{yes} b[/math]
11 [math]\$'[/math] [math]\#_{yes} \$ \$'[/math]

Решение МПСП будет иметь следующий вид:

Шаг Индекс элемента Первая строка Вторая строка
1 1 [math]\$ \#_{start} ab \$[/math] [math]\$[/math]
2 5 [math]\$ \#_{start} ab \$ b \#_{start}[/math] [math]\$ \#_{start} a[/math]
3 3 [math]\$ \#_{start} ab \$ b \#_{start} b[/math] [math]\$ \#_{start} ab[/math]
4 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$[/math] [math]\$ \#_{start} ab \$[/math]
5 3 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b[/math] [math]\$ \#_{start} ab \$ b[/math]
6 6 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b[/math] [math]\$ \#_{start} ab \$ b \#_{start} b[/math]
7 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$[/math]
8 8 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}[/math]
9 3 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b[/math]
10 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$[/math]
11 10 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b[/math]
12 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$[/math]
13 11 [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'[/math]
Лемма:
Универсальный язык сводится к МПСП.
Доказательство:
[math]\triangleright[/math]

Из определения m-сведения следует, что мы должны доказать, что машина Тьюринга [math]M[/math] допускает [math]w[/math] тогда и только тогда, когда построенный экземпляр МПСП имеет решение.

[math]\Rightarrow[/math]

Если [math]w[/math] допускается [math]M[/math], то можно проимитировать работу [math]M[/math] со входом [math]w[/math] и, как показано в примере выше, получить равные строки из элементов списков [math]A[/math] и [math]B[/math]. То есть найти решение МПСП.

[math]\Leftarrow[/math]

Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, и, как было сказано выше, если в первой строке никогда не будет символа [math]\#_{yes}[/math], то "сравнять" строки по длине не удастся. Значит, если МПСП имеет решение, то символ [math]\#_{yes}[/math] рано или поздно появится. А значит и машина Тьюринга допустит [math]w[/math].
[math]\triangleleft[/math]
Теорема:
ПСП не разрешима.
Доказательство:
[math]\triangleright[/math]
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.
[math]\triangleleft[/math]

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0
  • Wikipedia — Post correspondence problem