333
правки
Изменения
Нет описания правки
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем следующие правила:
<tex>q_nt q_n c \rightarrow q_n </tex> для <tex> \forall c \in T</tex>
<tex>q_n \rangle \rightarrow w \rangle </tex>, где для <tex> w \notin T </tex>
<tex> tw c w \rightarrow w </tex> для <tex> \forall t c \in T</tex>.
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* \langle w \rangle </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
