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

Эта статья находится в разработке!

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

Существует упорядоченная пара конечных последовательностей [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]\triangleright[/math]

Докажем неразрешимость: Сначала докажем для случая, когда [math]i_1 = 1[/math]. Считаем, что МТ никогда не приходит в N. MT: [math](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]\$ \ldots[/math] Если MT остановился, добъёмся того, что зак. Иначе стр будут расти до бесконечности, но никогда не зак [math]\forall c \in \Pi[/math] заведём пару [math](a_i=c b_i = c), (a_i = \$ b = \$)[/math] [math]a_i = d \#_p[/math], [math]b_i = \#_q c[/math], [math]\delta(q, c) = \lt p, d, \rightarrow\gt [/math] [math]a_i = \#_p a d[/math], [math]b_i a \#_q e[/math] [math]\delta (a, c) = \lt p, d, \leftarrow\gt [/math]. Аналогично переход на месте, или считаем, что таких не бывает.

[math]\triangleleft[/math]

Верно:

• умеем 1ПСП [math]\Rightarrow[/math] умеем ПСП
• не умеем 1ПСП [math]\Leftarrow[/math]не умеем ПСП

Надо:

• не умеем 1ПСП [math]\Rightarrow[/math] не умеем ПСП

Возьмём экземпляр задачи 1ПСП: [math](( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))[/math]. Вставим между каждой парой символов во всех строках символ [math]*[/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 = 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](a_1, b_1)[/math], т.к. все остальные пары начинаются с различных символов.

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

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

Литература

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