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

2014-12-28T11:48:59Z

5.175.93.46: english term

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

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

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

{{Определение
|definition=
Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов <tex>i_1 = 1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.
}}

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

{{Теорема
|statement=
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
|proof=
Для списков <tex>A</tex> и <tex>B</tex> размера <tex>n</tex> из условия ПСП построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
for <tex>m = 1 .. \infty</tex>
for all <tex>(i_1, i_2, \ldots, i_m): 1 \leq i_j \leq n</tex>
if <tex>a_{i_1} \ldots a_{i_m} = b_{i_1} \ldots b_{i_m}</tex>
return true
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
}}

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

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

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

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

Пусть даны списки <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 \ldots 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 \ldots 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-
|statement=
МПСП для пары списков <tex>(A, B)</tex> сводится к ПСП для пары списков <tex>(C, D)</tex>.
|proof=
Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП.

<tex>\Rightarrow</tex>

Пусть набор индексов <tex>(1, i_2, \ldots, i_k)</tex> - решение МПСП из условия леммы. То есть <tex>w_A = w_B</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}</tex>.

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

<tex>\# c_1 c_{i_2} \ldots c_{i_k} = d_1 d_{i_2} \ldots d_{i_k} \# </tex>.

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

<tex> c_0 c_{i_2} \ldots c_{i_k} c_{n+1} = d_0 d_{i_2} \ldots d_{i_k} d_{n+1} </tex>.

Итого, если <tex>(1, i_2, \ldots, i_k)</tex> - решение исходной МПСП, то <tex>(0, i_2, \ldots, i_k, n+1)</tex> - решение построенной по правилам выше ПСП.

<tex>\Leftarrow</tex>

В любом существующем решении ПСП для списков <tex>C, D</tex> должны выполняться условия:
* <tex>i_1 = 0</tex>, так как только в паре <tex>(c_1, d_1)</tex> первые символы совпадают;
* последний индекс равен <tex>n+1</tex>, так как только в паре <tex>(c_{n+1}, d_{n+1})</tex> строки заканчиваются одинаковыми символами.

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

<tex>c_0 c_{i_2} \ldots c_{i_k} c_{n+1} = d_0 d_{i_2} \ldots d_{i_k} d_{n+1}</tex>.

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

<tex>\# c_1 c_{i_2} \ldots c_{i_{f-1}}\$</tex> <tex>=</tex> <tex>d_1 d_{i_2} \ldots d_{i_{f-1}} \#\$</tex>.

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

<tex>a_1 a_{i_2} \ldots a_{i_{f-1}} = b_1 b_{i_2} \ldots b_{i_{f-1}}</tex>.

Итого, если <tex>(0, i_2, \ldots, i_k, n+1)</tex> - решение ПСП, то <tex>(1, i_2, \ldots, i_k)</tex> - решение исходной МПСП.
}}

Теперь покажем как свести универсальный язык к МПСП.
{{Определение
|definition=
Назовём '''снимком''' состояния МТ строку вида <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>\#_p</tex>.
}}
Построим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$</tex>,

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

Сформируем списки <tex>A</tex> и <tex>B</tex> по МТ <tex>M</tex> и входной строке <tex>w</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>B</tex> вынуждена постоянно "догонять" первую. Более того, можно заметить, что вторая строка всегда будет отставать ровно на один снимок. Действительно, первая пара из списков <tex>A</tex> и <tex>B</tex> задает это отставание. Затем при помощи элементов из правил <tex>4</tex>, <tex>5</tex> и <tex>6</tex> мы имитируем переход машины Тьюринга, добавляя во вторую строку то состояние и положение головки, которые были до перехода, а в первую строку - то состояние, положение головки и новый ленточный символ, которые стали после перехода. Нетрудно заметить, что тем самым строка составленная из элементов списка <tex>B</tex> будет соответствовать строке из элементов списка <tex>A</tex>, но с отставанием на один переход. Далее с помощью элементов из правил <tex>2</tex> и <tex>3</tex> мы допишем в обе строки одинаковые суффиксы текущего снимка, разделитель <tex>\$</tex> и префикс нового снимка до следующего перехода машины Тьюринга. Таким образом если первая строка равна

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex>,

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

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex>,

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

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n+1} \$</tex>

и

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$ snap_n \$</tex>,

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

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

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

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$</tex>

и

<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ </tex>.

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

=== Пример ===

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

<tex>\delta (start, a) = \langle start, b, \rightarrow \rangle</tex>;

<tex>\delta (start, b) = \langle yes, b, \downarrow \rangle</tex>;

из <tex>yes</tex> переходов нет.

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

{|class="wikitable" style="text-align: center"
|-
! Номер элемента
! Список A
! Список B
|-
|1
|<tex>\$ \#_{start} ab \$</tex>
|<tex>\$</tex>
|-
|2
|<tex>a</tex>
|<tex>a</tex>
|-
|3
|<tex>b</tex>
|<tex>b</tex>
|-
|4
|<tex>\$</tex>
|<tex>\$</tex>
|-
|5
|<tex>b \#_{start}</tex>
|<tex>\#_{start} a</tex>
|-
|6
|<tex>\#_{yes} b</tex>
|<tex>\#_{start} b</tex>
|-
|7
|<tex>\#_{yes}</tex>
|<tex>a \#_{yes}</tex>
|-
|8
|<tex>\#_{yes}</tex>
|<tex>b \#_{yes}</tex>
|-
|9
|<tex>\#_{yes}</tex>
|<tex>\#_{yes} a</tex>
|-
|10
|<tex>\#_{yes}</tex>
|<tex>\#_{yes} b</tex>
|-
|11
|<tex>\$'</tex>
|<tex>\#_{yes} \$ \$'</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>
|-
|align="center" | 11
|align="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>\$ \#_{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" | 13
|align="center" | 11
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>
|}

{{Лемма
|statement=
Универсальный язык сводится к МПСП.
|proof=
Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать, что машина Тьюринга <tex>M</tex> допускает <tex>w</tex> тогда и только тогда, когда построенный экземпляр МПСП имеет решение.

<tex>\Rightarrow</tex>

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

<tex>\Leftarrow</tex>

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

}}

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

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

Викиконспекты - Вклад участника [ru]

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