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

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

Дана упорядоченная пара конечных последовательностей [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_n, b_n[/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]( 1 , i_1, \ldots , i_k )[/math], удовлетворяющих условию [math]a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, [/math] при [math] 1 \leq i_j \leq n[/math] [math]\forall j[/math] для упорядоченной пары конечных последовательностей [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]\forall i[/math].

Считаем, что Машина Тьюринга ([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]\Rightarrow[/math] существует решение ПСП
• Не существует решения МПСП [math]\Leftarrow[/math]не существует решения ПСП

Необходимо:

• Не существует решения МПСП [math]\Rightarrow[/math] не существует решения ПСП

Возьмём экземпляр задачи МПСП: [math](( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))[/math]. Вставим между каждой парой символов во всех строках символ [math]*[/math].

[math]i = 1[/math]

• [math]a_1 = * c_1 * c_2 \ldots c_l *[/math]
• [math]b_1 = * c_1 * c_2 \ldots c_l[/math]

[math]i = 2 \ldots n [/math]:

• [math]a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *[/math]
• [math]b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l[/math]

[math]i = n + 1[/math]

• [math]a_{n+1} = \$[/math]
• [math]b_{n+1} = *\$[/math]

Теперь необходимо начать с [math](a_1, b_1)[/math], т.к. все остальные пары начинаются с различных символов.

Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, в которой всё начиналось с пары [math](a_1, b_1)[/math].

Литература

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