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

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

Основные определения

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

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

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

Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов [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, \ldots, i_m): 1 \leq i_j \leq n[/math] if [math]a_{i_1} \ldots a_{i_m} = b_{i_1} \ldots 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 \ldots 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 \ldots 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, \ldots, i_k)[/math] - решение МПСП из условия леммы. То есть [math]w_A = w_B[/math], где [math]w_A = a_1 a_{i_2} \ldots a_{i_k}[/math], [math]w_B = b_1 b_{i_2} \ldots b_{i_k}[/math]. Рассмотрев цепочки [math]w_C[/math] и [math]w_D[/math] c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа [math]\#[/math] в начале, а второй - в конце. Конкретно, [math]\# c_1 c_{i_2} \ldots c_{i_k} = d_1 d_{i_2} \ldots d_{i_k} \# [/math]. Изменив первый индекс с [math]1[/math] на [math]0[/math], решим проблему с символом [math]\#[/math] в начале. Добавив индекс [math]n+1[/math] к набору, решим проблему с символом [math]\#[/math] в конце. [math] c_0 c_{i_2} \ldots c_{i_k} c_{n+1} = d_1 d_{i_2} \ldots d_{i_k} d_{n+1} [/math]. Итого, если [math](1, i_2, \ldots, i_k)[/math] - решение исходной МПСП, то [math](0, i_2, \ldots, 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, \ldots, i_k, n + 1)[/math] является решением ПСП. Иными словами, [math]c_0 c_{i_2} \ldots c_{i_k} c_{n+1} = d_0 d_{i_2} \ldots d_{i_k} d_{n+1}[/math]. Если [math]i_f[/math] — наименьший индекс, равный [math]n+1[/math], то [math]c_0 c_{i_2} \ldots c_{i_f}[/math], [math]d_0 d_{i_2} \ldots d_{i_f}[/math] — префиксы исходных конкатенаций до первого символа [math]\$[/math], следовательно, равны между собой. Последовательность [math](0, i_{2} \ldots, 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} \ldots c_{i_{f-1}}\$[/math] [math]=[/math] [math]d_1 d_{i_2} \ldots d_{i_{f-1}} \#\$[/math]. Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца [math]\$[/math], получим [math]a_1 a_{i_2} \ldots a_{i_{f-1}} = b_1 b_{i_2} \ldots b_{i_{f-1}}[/math]. Итого, если [math](0, i_2, \ldots, i_k, n+1)[/math] - решение ПСП, то [math](1, i_2, \ldots, i_k)[/math] - решение исходной МПСП.

[math]\triangleleft[/math]

Лемма:

Универсальный язык сводится к МПСП.

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

[math]\triangleright[/math]

Выполним m-сведение универсального языка к МПСП со списками [math]A[/math] и [math]B[/math]. Назовём снимком состояния МТ строку вида [math]c_1 c_2 \ldots c_k \#_p c_{k+1} \ldots c_t[/math], где [math]c_1 c_2 \ldots c_t[/math] — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, [math]p[/math] — текущее состояние автомата МТ, головка расположена справа от [math]\#_p[/math]. Построим последовательности таким образом, чтобы решение МПСП образовывало строку [math]\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$'[/math], где [math]snap_i[/math] — снимки последовательных состояний МТ от стартового до конечного, [math]snap_{n_{-t}}[/math] — последний снимок с [math]t[/math] удалёнными символами. Оговоримся, что состояния [math]no[/math] в автомате МТ не существует (его роль может выполнять сток), допуск происходит при попадании в состояние [math]yes[/math]. Сформируем последовательности [math]a[/math] и [math]b[/math] по МТ [math]M[/math] и строке [math]w[/math]. [math]a_1 = \$' \#_{start} w \$ [/math], [math]b_1 = \$'[/math]; для всех символов [math]c[/math] алфавита ленты: [math]a_i = c[/math], [math]b_i = c[/math], а также [math]a_i = \$[/math], [math]b_i = \$[/math]; для всех правил [math]M[/math] вида [math]\delta (p, c) = \langle q, d, \leftarrow \rangle[/math] и для всех символов алфавита [math]e[/math]: [math]a_i = \#_q e d[/math], [math]b_i = e \#_p c[/math]; для всех правил [math]M[/math] вида [math]\delta (p, c) = \langle q, d, \rightarrow \rangle[/math]: [math]a_i = d \#_q[/math], [math]b_i = \#_p c[/math]; для всех правил [math]M[/math] вида [math]\delta (p, c) = \langle q, d, \downarrow \rangle[/math]: [math]a_i = \#_q d[/math], [math]b_i = \#_p c[/math]. Заметим, что все элементы [math]a[/math] и [math]b[/math], кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов [math]a[/math], всегда оказывается длиннее. Если представить процесс формирования решения МПСП как динамический, вторая строка вынуждена постоянно «догонять» первую. Более того, можно доказать по индукции, что если первая строка имеет вид [math]\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$[/math], то вторая будет равна [math]\$' snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$[/math], а через несколько шагов они изменятся на [math]\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n+1} \$[/math] и [math]\$' snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$ snap_n \$[/math], соответственно. Задача — получить равные строки, если состояние [math]\#_{yes}[/math] достижимо. Для этого добавим в уже имеющиеся последовательности следующие элементы: для всех символов [math]c[/math] алфавита ленты: [math]a_i = \#_{yes}[/math], [math]b_i = \#_{yes} c[/math], [math]a_i = \#_{yes}[/math], [math]b_i = c \#_{yes}[/math], а также [math]a_i = \$'[/math], [math]b_i = \#_{yes} \$ \$'[/math]. Если состояние [math]yes[/math] недостижимо, в первой строке никогда не будет символа [math]\#_{yes}[/math], и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину. Если же допускающее состояние встретится, с помощью новых элементов можно будет привести обе строки к виду [math]\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$'[/math]. Другими словами, «сравнять» строки возможно тогда и только тогда, когда автомат, принадлежащий [math]M[/math], допускает [math]w[/math]. Таким образом, выполнено успешное m-сведение множества пар из машины Тьюринга (МТ) [math]M[/math] и строки [math]w[/math], где [math]M(w)[/math] не зависает, к множеству решений МПСП.

[math]\triangleleft[/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]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]

По доказанному ранее, МПСП неразрешима. Тогда, вследствие теоремы для m-сведения, ПСП неразрешима. }}

Источники

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