153
правки
Изменения
Нет описания правки
|statement=
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.
(Не существует пример примера неразрешимого языка, который является языком программ)
|proof=
Докажем неразрешимость:
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''МТМашина Тьюринка''' (<tex>MT</tex>) никогда не приходит в '''<tex>N'''</tex>. '''MT''': <tex>MT: (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>\$ 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>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> не умеем '''ПСП'''
