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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 59: Строка 59:
 
<tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex>.
 
<tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex>.
  
−
Такие последовательности позволяют сформировать строки <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex> (из <tex>a</tex>) и <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex> (из <tex>b</tex>), но решения МПСП быть не может, так как все члены последовательностей, кроме первого, имеют равную длину, и строка, составленная из элементов <tex>a</tex>, всегда оказывается длиннее.
+
Такие последовательности позволяют сформировать строки <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex> (из <tex>a</tex>) и <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex> (из <tex>b</tex>) и только их, но решения МПСП быть не может, так как все члены последовательностей, кроме первого, имеют равную длину, и строка, составленная из элементов <tex>a</tex>, всегда оказывается длиннее.
  
 
Задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности следующие элементы:
 
Задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности следующие элементы:
Строка 71: Строка 71:
 
а также
 
а также
  
−
<tex>a_i = \$ \$</tex>, <tex>b_i = <tex> \#_{yes} \$ \$</tex>.
+
<tex>a_i = \$</tex>, <tex>b_i = <tex> \#_{yes} \$ \$</tex>.
  
 
С помощью новых элементов можно привести обе строки к виду  
 
С помощью новых элементов можно привести обе строки к виду  
Строка 95: Строка 95:
 
{| border="1"
 
{| border="1"
 
  |Номер элемента
 
  |Номер элемента
−
  |width="45"|1
+
  |width="60"|1
−
  |width="45"|2
+
  |width="60"|2
−
  |width="45"|3
+
  |width="60"|3
−
  |width="45"|4
+
  |width="60"|4
−
  |width="45"|5
+
  |width="60"|5
−
  |width="45"|6
+
  |width="60"|6
−
  |width="45"|7
+
  |width="60"|7
−
  |width="45"|8
+
  |width="60"|8
−
  |width="45"|9
+
  |width="60"|9
−
  |width="45"|10
+
  |width="60"|10
−
  |width="45"|11
+
  |width="60"|11
 
  |-
 
  |-
 
  |Последовательность a
 
  |Последовательность a
−
  |<tex>\$ \#_{start} a \$</tex>
+
  |<tex>\$ \#_{start} ab \$</tex>
 
  |<tex>a</tex>
 
  |<tex>a</tex>
 
  |<tex>b</tex>
 
  |<tex>b</tex>
Строка 118: Строка 118:
 
  |<tex>\#_{yes}</tex>
 
  |<tex>\#_{yes}</tex>
 
  |<tex>\#_{yes}</tex>
 
  |<tex>\#_{yes}</tex>
−
  |<tex>\$ \$</tex>
+
  |<tex>\$</tex>
 
  |-
 
  |-
 
  |Последовательность b
 
  |Последовательность b
Строка 134: Строка 134:
 
  |}
 
  |}
  
 +
Решение МПСП будет иметь следующий вид:
 +
 +
{| border="1"
 +
|Шаг
 +
|Индекс элемента
 +
|Первая строка
 +
|Вторая строка
 +
|-
 +
|1
 +
|1
 +
|<tex>\$ \#_{start} ab \$</tex>
 +
|<tex>\$</tex>
 +
|-
 +
|2
 +
|5
 +
|<tex>\$ \#_{start} ab \$ b \#_{start}</tex>
 +
|<tex>\$ \#_{start} a</tex>
 +
|-
 +
|3
 +
|3
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
 +
|<tex>\$ \#_{start} ab</tex>
 +
|-
 +
|4
 +
|4
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$</tex>
 +
|<tex>\$ \#_{start} ab \$</tex>
 +
|-
 +
|5
 +
|3
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b</tex>
 +
|<tex>\$ \#_{start} ab \$ b</tex>
 +
|-
 +
|6
 +
|6
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex>
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
 +
|-
 +
|7
 +
|4
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex>
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$</tex>
 +
|-
 +
|8
 +
|8
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex>
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex>
 +
|-
 +
|9
 +
|3
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex>
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>
 +
|-
 +
|10
 +
|4
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex>
 +
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>
 +
|-
 +
|11
 +
|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>
 +
|-
 +
|12
 +
|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>
 +
|-
 +
|13
 +
|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>
 +
|}
  
  

Версия 09:09, 21 января 2012

Определение:
Дана упорядоченная пара конечных последовательностей [math]((a_1, \ldots, a_n), (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, называется проблемой соответствий Поста (ПСП). Такую последовательность индексов, в случае её существования, называют решением проблемы соответствий Поста.


Определение:
Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов [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]\triangleright[/math]

Выполним m-сведение множества пар из машины Тьюринга (МТ) [math]M[/math] и строки [math]w[/math], где [math]M(w)[/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]\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$[/math] (из [math]a[/math]) и [math]\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$[/math] (из [math]b[/math]) и только их, но решения МПСП быть не может, так как все члены последовательностей, кроме первого, имеют равную длину, и строка, составленная из элементов [math]a[/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 = \lt tex\gt \#_{yes} \$ \$[/math].

С помощью новых элементов можно привести обе строки к виду

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

но только тогда, когда в [math]snap_n[/math] содержится [math]\#_{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] будут сформированы следующим образом:

Номер элемента 1 2 3 4 5 6 7 8 9 10 11
Последовательность a [math]\$ \#_{start} ab \$[/math] [math]a[/math] [math]b[/math] [math]\$[/math] [math]b \#_{start}[/math] [math]\#_{yes} b[/math] [math]\#_{yes}[/math] [math]\#_{yes}[/math] [math]\#_{yes}[/math] [math]\#_{yes}[/math] [math]\$[/math]
Последовательность b [math]\$[/math] [math]a[/math] [math]b[/math] [math]\$[/math] [math]\#_{start} a[/math] [math]\#_{start} b[/math] [math]a \#_{yes}[/math] [math]b \#_{yes}[/math] [math]\#_{yes} a[/math] [math]\#_{yes} b[/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]a, b[/math] из условия МПСП. Обозначим как [math]left(w, c)[/math] и [math]right(w, c)[/math] строки, состоящие из символов [math]w[/math], разделённых [math]c[/math]: [math]left(w, c) = c w_1 c w_2 \ldots c w_k[/math], [math]right(w, c) = w_1 c w_2 c \dots w_k c[/math].

Построим две новые последовательности [math]a', b'[/math]:

  • [math]a'_1 = \$ right(a_1, \$)[/math], [math]b'_1 = left(b_1, \$)[/math];
  • [math]\forall i = 1 .. n[/math]: [math]a'_{i+1} = right(a_i, \$)[/math], [math]b'_{i+1} = left(b_i, \$)[/math];
  • [math]a'_{n+2} = \#[/math], [math]b'_{n+2} = \$ \#[/math],

где [math]\$[/math], [math]\#[/math] — символы, не встречающиеся в словах исходных последовательностей.

Утверждение:
Существование решения МПСП для [math]a, b[/math] эквивалентно существованию решения ПСП для [math]a', b'[/math].
[math]\triangleright[/math]

[math]\Rightarrow[/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_a = w_b[/math]. Рассмотрим

[math]w'_a = a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = \$ right(a_1, \$) right(a_{i_2}, \$) \ldots right(a_{i_k}, \$) \#[/math],

[math]w'_b = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2} = left(b_1, \$) left(b_{i_2}, \$) \ldots left(b_{i_k}, \$) \$ \#[/math].

На чётных позициях в [math]w'_a[/math] и [math]w'_b[/math] стоят равные символы из [math]w_a[/math] и [math]w_b[/math], а также [math]\#[/math] (в конце); на нечётных — [math]\$[/math]. Следовательно, [math]w'_a = w'_b[/math], то есть

[math]a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2}[/math].

[math]\Leftarrow[/math]

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

  • [math]i_1 = 1[/math], так как только в паре [math](a'_1, b'_1)[/math] первые символы совпадают;
  • последний индекс равен [math]n+2[/math], так как только в паре [math](a'_{n+2}, b'_{n+2})[/math] строки заканчиваются одинаковыми символами.

Пусть

[math]a'_1 a'_{i_2} \ldots a'_{i_k} = b'_1 b'_{i_2} \ldots b'_{i_k}[/math].

Если [math]i_f[/math] — наименьший индекс, равный [math]n+2[/math], то [math]a'_1 a'_{i_2} \ldots a'_{i_f}[/math], [math]b'_1 b'_{i_2} \ldots b'_{i_f}[/math] — префиксы исходных конкатенаций до первого символа [math]\#[/math], следовательно, равны между собой. [math]i_1, \ldots, i_f[/math] — также решение ПСП, причём [math]i_1 = 1[/math], [math]i_f = n + 2[/math]. Остальные индексы не превосходят [math]n+1[/math], но и не равны [math]1[/math], иначе в левой части равенства образуется подстрока из двух [math]\$[/math] подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:

[math]\$ right(a_1, \$) right(a_{i_2-1}, \$) \ldots right(a_{i_{f-1}-1}, \$) \#[/math] [math]=[/math] [math]left(b_1, \$) left(b_{i_2-1}, \$) \ldots left(b_{i_{f-1}-1}, \$) \$ \#[/math].

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

[math]a_1 a_{i_2-1} \ldots a_{i_{f-1}-1} = b_1 b_{i_2-1} \ldots b_{i_{f-1}-1}[/math].
[math]\triangleleft[/math]
По доказанному ранее, МПСП неразрешима. Тогда, вследствие теоремы для m-сведения, ПСП неразрешима.
[math]\triangleleft[/math]

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Примеры_неразрешимых_задач:_проблема_соответствий_Поста&oldid=17467»