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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 13: Строка 13:
 
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
 
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
 
|proof=
 
|proof=
Пусть даны последовательности <tex>a_n, b_n</tex> из условия ПСП. Количество последовательностей индексов, каждый из которых находится в пределах от 1 до <tex>n</tex>, длины <tex>m</tex> равно <tex>n^m</tex>. Программа-полуразрешитель <tex>p</tex> устроена следующим образом:
+
Пусть даны последовательности <tex>a, b</tex> из условия ПСП. Количество последовательностей индексов, каждый из которых находится в пределах от 1 до <tex>n</tex>, длины <tex>m</tex> равно <tex>n^m</tex>. Программа-полуразрешитель <tex>p</tex> устроена следующим образом:
 
   for <tex>m = 1 .. \infty</tex>
 
   for <tex>m = 1 .. \infty</tex>
 
     for all <tex>(i_1, i_2, \ldots, i_m): 1 \leq i_j \leq n</tex>
 
     for all <tex>(i_1, i_2, \ldots, i_m): 1 \leq i_j \leq n</tex>
Строка 64: Строка 64:
 
Выполним [[M-сводимость|m-сведение]] множества решений МПСП к множеству решений ПСП.
 
Выполним [[M-сводимость|m-сведение]] множества решений МПСП к множеству решений ПСП.
  
Пусть даны последовательности <tex>a_n, b_n</tex> из условия МПСП. Построим две новые последовательности <tex>a'_{n+2}, b'_{n+2}</tex>:
+
Пусть даны последовательности <tex>a, b</tex> из условия МПСП. Построим две новые последовательности <tex>a', b'</tex>:
 
* <tex>a'_1 = \$ a_1 \$</tex>, <tex>b'_1 = \$ b_1</tex>;
 
* <tex>a'_1 = \$ a_1 \$</tex>, <tex>b'_1 = \$ b_1</tex>;
 
* <tex>\forall i = 1 .. n</tex>: <tex>a'_{i+1} = a_i \$</tex>, <tex>b'_{i+1} = \$ b_i</tex>;
 
* <tex>\forall i = 1 .. n</tex>: <tex>a'_{i+1} = a_i \$</tex>, <tex>b'_{i+1} = \$ b_i</tex>;

Версия 22:11, 9 января 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, b[/math] из условия ПСП. Количество последовательностей индексов, каждый из которых находится в пределах от 1 до [math]n[/math], длины [math]m[/math] равно [math]n^m[/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 1
Таким образом, язык пар указанных последовательностей полуразрешим, а значит, перечислим.
[math]\triangleleft[/math]

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

Теорема:
МПСП неразрешима.
Доказательство:
[math]\triangleright[/math]

Выполним m-сведение множества строк, на которых заданная машина Тьюринга (МТ) не зависает, к множеству решений МПСП.


Считаем, что Машина Тьюринга ([math]MT[/math]) никогда не приходит в [math]N[/math] - недопуск. [math]MT: (m, \omega)[/math]. Задача [math]m(\omega) = Y[/math] не разрешима. Предположим, что мы умеем решать МПСП.

[math]a_1 = \$ \#_s \omega \$[/math], [math]b_1 = \$[/math]. Таким образом выводятся следующие последовательности: [math]\$ A_0 \$ \ldots \$ A_k \$[/math] и [math]\$ A_i \ldots[/math] - мгновенное описание.

Если [math]MT[/math] остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.

[math]\forall c \in \Pi[/math] построим следующую пару [math](a_i=c, b_i = c), (a_i = \$, b = \$)[/math]. [math]b[/math] должно сойтись с соответствующей [math]a[/math] в предыдущем мгновенном описании.

Соответственно [math]a_i = d \#_p[/math], [math]b_i = \#_q c[/math] и [math]\delta(q, c) = \langle p, d, \rightarrow \rangle[/math], а также [math]a_i = \#_p a d[/math], [math]b_i a \#_q e[/math] и [math]\delta (a, c) = \langle p, d, \leftarrow \rangle [/math]. Аналогично следует поступить и с переходом на месте, или считаем, что такого не бывает.

Как может быть устроен префикс решения МПСП:

[math]a[/math]: [math]| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |[/math]

[math]b[/math]: [math]| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |[/math]

Требуется добиться остановки. Для этого добавляется далее:

  • [math]a = \#_y[/math], [math]b = \#_y c[/math]
  • или [math]a = \#_y[/math], [math]b = c \#_y[/math]
  • или [math]a = \$[/math], [math]b = \#_y \$ \$[/math]

[math]\triangleleft[/math]
Теорема:
ПСП неразрешима.
Доказательство:
[math]\triangleright[/math]

Выполним m-сведение множества решений МПСП к множеству решений ПСП.

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

  • [math]a'_1 = \$ a_1 \$[/math], [math]b'_1 = \$ b_1[/math];
  • [math]\forall i = 1 .. n[/math]: [math]a'_{i+1} = a_i \$[/math], [math]b'_{i+1} = \$ 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]a_1 a_{i_2} \ldots a_{i_k} = b_1 b_{i_2} \ldots b_{i_k}[/math]. Тогда [math]a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = \$ a_1 \$ a_{i_2} \$ \ldots \$ a_{i_k} \$ \#[/math], [math]b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2} = \$ b_1 \$ b_{i_2} \$ \ldots \$ b_{i_k} \$ \#[/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]\$ 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]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]

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.