Примеры неразрешимых задач: проблема соответствий Поста — различия между версиями
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | + | Существует упорядоченная пара конечных последовательностей <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, называется '''проблемой соответствий Поста (ПСП)'''. | |
}} | }} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | + | Язык имеющих решение проблем соответствий поста перечислим, но не разрешим. | |
+ | (Не существует пример неразрешимого языка, который является языком программ) | ||
|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
Определение: |
Существует упорядоченная пара конечных последовательностей | , где и для всех . Вопрос существования непустой последовательности индексов , удовлетворяющей условию , где для каждого j, называется проблемой соответствий Поста (ПСП).
Теорема: |
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.
(Не существует пример неразрешимого языка, который является языком программ) |
Доказательство: |
Докажем неразрешимость: Сначала докажем для случая, когда . Считаем, что МТ никогда не приходит в N. MT: . Задача не разрешима. Предположим, что мы умеем решать ПСП., . , Если MT остановился, добъёмся того, что зак. Иначе стр будут расти до бесконечности, но никогда не зак заведём пару , , Аналогично переход на месте, или считаем, что таких не бывает. , . |
Верно:
- умеем 1ПСП умеем ПСП
- не умеем 1ПСП не умеем ПСП
Надо:
- не умеем 1ПСП не умеем ПСП
Возьмём экземпляр задачи 1ПСП:
. Вставим между каждой парой символов во всех строках символ .:
Нужно начать с
, т.к. все остальные пары начинаются с различных символов.Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары
.Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.