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

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

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

Даны два конечных списка

$A = (a_1, \dots, a_n)$ и

$B = (b_1 ,\dots ,b_n)$ , где

$a_i \in \Sigma ^*$ и

$b_i \in \Sigma ^*$ для всех

$i$ . Вопрос существования непустой последовательности индексов

$(i_1 , \dots, i_k)$ , удовлетворяющей условию

$a_{i_1} \dots a_{i_k} = b_{i_1} \dots b_{i_k}$ , где

$1 \leqslant i_j \leqslant n$ для всех

$j$ , называется проблемой соответствий Поста (ПСП). Такую последовательность индексов, в случае её существования, называют решением проблемы соответствий Поста.

Содержание

[убрать]

1 Примеры решений проблем соответсвия Поста
2 Перечислимость языка ПСП
3 Неразрешимость языка ПСП
- 3.1 Пример
4 См. также
5 Источники информации

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

$1)$

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

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

$sA = 01, 11, 101, 1$

$sB = 0, 111, 10, 11$

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

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

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

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

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

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

Теорема:

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

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

$\triangleright$

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

 for  $m = 1 .. \infty$ 
   foreach  $(i_1, i_2, \dots, i_m): 1 \leqslant i_j \leqslant n$ 
     if  $a_{i_1} \dots a_{i_m} = b_{i_1} \dots b_{i_m}$ 
       return true

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

$\triangleleft$

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

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

Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов

$i_1 = 1$ , называется модифицированной проблемой соответствий Поста (МПСП).

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

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

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

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

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

Лемма:

МПСП для пары списков

$(A, B)$ сводится к ПСП для пары списков

$(C, D)$ .

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

$\triangleright$

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

$\Rightarrow$

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

$w_A = a_1 a_{i_2} \dots a_{i_k}$ ,

$w_B = b_1 b_{i_2} \dots b_{i_k}$ .

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

$\# c_1 c_{i_2} \dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \#$ .

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

$c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1}$ .

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

$\Leftarrow$

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

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

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

$c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1}$ .

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

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

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

$a_1 a_{i_2} \dots a_{i_{f-1}} = b_1 b_{i_2} \dots b_{i_{f-1}}$ .

Итого, если

$(0, i_2, \dots, i_k, n+1)$ — решение ПСП, то

$(1, i_2, \dots, i_k)$ — решение исходной МПСП.

$\triangleleft$

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

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

Назовём снимком состояния МТ строку вида

$c_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t$ , где

$c_1 c_2 \dots c_t$ — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа,

$p$ — текущее состояние автомата МТ, головка расположена справа от

$\#_p$ .

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

,

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

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

1.

$a_1 = \$ \#_{start} w \$$ ,

$b_1 = \$$ . По определению МПСП эта пара всегда будет первой в любом решении.

2.

$a_i = c$ ,

$b_i = c$ для всех символов

$c$ алфавита ленты.

3.

$a_i = \$$ ,

$b_i = \$$ .

4.

$a_i = \#_q e d$ ,

$b_i = e \#_p c$ для всех правил

$M$ вида

$\delta (p, c) = \langle q, d, \leftarrow \rangle$ и для всех символов алфавита

$e$ .

5.

$a_i = d \#_q$ ,

$b_i = \#_p c$ для всех правил

$M$ вида

$\delta (p, c) = \langle q, d, \rightarrow \rangle$ .

6.

$a_i = \#_q d$ ,

$b_i = \#_p c$ для всех правил

$M$ вида

$\delta (p, c) = \langle q, d, \downarrow \rangle$ .

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

$\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$$ ,

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

$\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$$ ,

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

$\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n+1} \$$

и

$\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$ snap_n \$$ ,

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

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

7.

$a_i = \#_{yes}$ ,

$b_i = \#_{yes} c$ , для всех символов

$c$ алфавита ленты.

8.

$a_i = \#_{yes}$ ,

$b_i = c \#_{yes}$ , для всех символов

$c$ алфавита ленты.

9.

$a_i = \$'$ ,

$b_i = \#_{yes} \$ \$'$ .

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

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

и

.

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

Пример

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

$\delta (start, a) = \langle start, b, \rightarrow \rangle$ ;

$\delta (start, b) = \langle yes, b, \downarrow \rangle$ ;

из $yes$ переходов нет.

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

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

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

Шаг	Индекс элемента	Первая строка	Вторая строка
1	1	$\$ \#_{start} ab \$$	$\$$
2	5	$\$ \#_{start} ab \$ b \#_{start}$	$\$ \#_{start} a$
3	3	$\$ \#_{start} ab \$ b \#_{start} b$	$\$ \#_{start} ab$
4	4	$\$ \#_{start} ab \$ b \#_{start} b\$$	$\$ \#_{start} ab \$$
5	3	$\$ \#_{start} ab \$ b \#_{start} b\$ b$	$\$ \#_{start} ab \$ b$
6	6	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b$	$\$ \#_{start} ab \$ b \#_{start} b$
7	4	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$$	$\$ \#_{start} ab \$ b \#_{start} b \$$
8	8	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}$	$\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}$
9	3	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b$	$\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b$
10	4	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$$	$\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$$
11	10	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}$	$\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b$
12	4	$\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$$	$\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$$
13	11

Лемма:

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

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

$\triangleright$

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

$\Rightarrow$

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

$\Leftarrow$

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

$\#_{yes}$ , то "сравнять" строки по длине не удастся. Значит, если МПСП имеет решение, то символ

$\#_{yes}$ рано или поздно появится. А значит и машина Тьюринга допустит

$w$ .

$\triangleleft$

Теорема:

ПСП не разрешима.

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

$\triangleright$

Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.

$\triangleleft$

См. также

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

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

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

Содержание

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

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

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

Пример

См. также

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты