Изменения

И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. При этом пусть это уникальное слово имеет вид состоит лишь из символа допускающего состояния <tex> \langle w \rangle </tex>, где <tex> w \notin T q_n </tex>. Таким образом, имеем следующие правила:

<tex>q_n c \rightarrow q_n </tex> и <tex>c q_n \rightarrow q_n </tex> для <tex> \forall c \in T\cup Q \cup \{B, \langle, \rangle \} </tex>

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