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

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

Определение:

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

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

Теорема:

Язык пар последовательностей, для которых существует решение ПСП, перечислим.

Доказательство:

[math]\triangleright[/math]

Для списков [math]A[/math] и [math]B[/math] размера [math]n[/math] из условия ПСП построим программу-полуразрешитель [math]p[/math], проверяющую все возможные решения: for [math]m = 1 .. \infty[/math] for all [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]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] будут сформированы следующим образом:

Номер элемента	Список A	Список B
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
• Post correspondence problem - Wikipedia