153
правки
Изменения
Нет описания правки
(Не существует примера неразрешимого языка, который является языком программ)
|proof=
Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатинацию и сравним. Сошлось - задача решена, иначе - программа зависла.
Докажем неразрешимость:
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>- недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = yY</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.
Если <tex>MT</tex> остановится, добьёмся того, что закчтобы строка закончилось. Иначе строки будут расти до бесконечности, но никогда не закончатся.
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.
<tex>b</tex> должно сойтись с соответствующей <tex>a</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 = \#_y</tex>, <tex>b = \#_y c</tex>
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex>
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex>
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.
}}
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
