Изменения

Перейти к: навигация, поиск

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

224 байта добавлено, 13:47, 23 декабря 2010
Нет описания правки
{{Определение
|definition=
'''Постовской системой соответствия над алфавитом <tex>\Sigma</tex>''' называется Существует упорядоченная пара конечных последовательностей <tex>(( x_1 a_1 , \ldots , x_n a_n ) , ( y_1 b_1 , \ldots , y_n b_n ))</tex>, где <tex>x_i a_i \in \Sigma ^*</tex> и <tex>x_i 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, называется '''iпроблемой соответствий Поста (ПСП)'''.
}}
{{Определение
|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=
Пусть <tex>| \Sigma | \geq 2</tex>. Тогда Язык имеющих решение проблем соответствий поста перечислим, но не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом <tex>\Sigma</tex> узнать, имеет ли она решениеразрешим. (Другими словамиНе существует пример неразрешимого языка, проблема соответствий Поста неразрешима.который является языком программ)
|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>.
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
Mamoshkin.Arseny
153
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/6204»

Навигация