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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Постовской системой соответствия над алфавитом <tex>\Sigma</tex>''' называется упорядоченная пара конечных последовательностей <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>, где <tex>x_i \in \Sigma ^*</tex> и <tex>x_i \in \Sigma ^*</tex> для всех '''i'''.
+
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.
 
}}
 
}}
{{Определение
 
|definition=
 
'''Решением постовской системы соответствия <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>''' называется непустая последовательность индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющая условию <tex>
 
x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j.
 
}}
 
===Пример===
 
Пусть <tex>\Sigma = \{ a , b , c \}</tex>. Рассмотрим постовскую систему соответствия <tex>((aab, a, caa),(a, aa, bc))</tex>.
 
Последовательность <tex>(2,1,3,2,2)</tex> является решением этой системы, так как <tex>a \cdot aab \cdot caa \cdot a \cdot a =
 
aa \cdot a \cdot bc \cdot aa \cdot aa</tex>.
 
{{Определение
 
|definition=
 
'''Проблемой соответствий Поста (ПСП)''' (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.
 
}}
 
===Модифицированная проблема соответствий поста===
 
Рассмотрим промежуточную версию ПСП, которая называется '''модифицированной проблемой соответствий Поста''', или '''МПСП'''. В 
 
модифицированной ПСП на решение накладывается дополнительное требование, чтобы первой парой в решении была пара первых элементов списков '''А''' и '''В'''. Более формально, экземпляр МПСП состоит из двух списков <tex>A = ( x_1 , \ldots , x_k )</tex> и <tex>B = ( y_k , \ldots , y_k )</tex>, и решением является последовательность из О или нескольких целых чисел <tex>i_1, \ldots, i_m</tex> при которой <tex>x_1 x_{i_1} \ldots x_{i_k} = y_1 y_{i_1} \ldots y_{i_m}</tex>
 
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть <tex>| \Sigma | \geq 2</tex>. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом <tex>\Sigma</tex> узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)
+
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.
 +
(Не существует пример неразрешимого языка, который является языком программ)
 
|proof=
 
|proof=
 +
Докажем неразрешимость:
  
 +
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''МТ''' никогда не приходит в '''N'''. '''MT''': <tex>(m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''ПСП'''.
 +
 +
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.
 +
<tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ \ldots</tex>
 +
 +
Если '''MT''' остановился, добъёмся того, что зак. Иначе стр будут расти до бесконечности, но никогда не зак
 +
 +
<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>.
 +
Аналогично переход на месте, или считаем, что таких не бывает.
 
}}
 
}}
  
 +
'''Верно''':
 +
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''
 +
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''
 +
'''Надо''':
 +
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''
 +
 +
Возьмём экземпляр задачи 1ПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.
 +
 +
<tex>i = 2 \ldots n </tex>:
 +
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex>
 +
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex>
 +
<tex>i = 1</tex>
 +
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex>
 +
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex>
 +
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.
 +
* <tex>a_{n+1} = \$</tex>
 +
* <tex>b_{n+1} = *\$</tex>
 +
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.
 
== Литература ==
 
== Литература ==
 
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
 
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.

Версия 13:47, 23 декабря 2010

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

Литература

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