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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
|statement=
 
|statement=
 
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.
 
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.
(Не существует пример неразрешимого языка, который является языком программ)
+
(Не существует примера неразрешимого языка, который является языком программ)
 
|proof=
 
|proof=
 
Докажем неразрешимость:
 
Докажем неразрешимость:
  
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''МТ''' никогда не приходит в '''N'''. '''MT''': <tex>(m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''ПСП'''.
+
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.
  
 
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.
 
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.
<tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ \ldots</tex>
+
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.
  
Если '''MT''' остановился, добъёмся того, что зак. Иначе стр будут расти до бесконечности, но никогда не зак
+
Если <tex>MT</tex> остановится, добъёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.
  
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>
+
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.
 +
 
 +
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.
 +
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.
  
<tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex>, <tex>\delta(q, c) = <p, d, \rightarrow></tex>
 
  
<tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex>
 
<tex>\delta (a, c) = <p, d, \leftarrow></tex>.
 
Аналогично переход на месте, или считаем, что таких не бывает.
 
 
}}
 
}}
  
 +
Теперь остаётся избавиться от требования фиксированного первого индекса:
 
'''Верно''':
 
'''Верно''':
 
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''
 
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''
 
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''
 
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''
'''Надо''':
+
'''Необходимо''':
 
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''
 
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''
  

Версия 16:53, 15 января 2011

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


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

Докажем неразрешимость:

Сначала докажем для случая, когда [math]i_1 = 1[/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]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].

Литература

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