Изменения

В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex>:

<tex>q| \rightarrow vDash q0| </tex> и <tex>|q \vDash |0q </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>  И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это позволит нам построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем следующие правила: <tex>q_nt \vDash q_n </tex> <tex>q_n| \vDash w| </tex>  <tex> tw \vDash w </tex> для <tex> \forall t \in T</tex>. Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме из слова <tex> |q_0u| </tex> выводится <tex> |w| </tex>. Таким образом из разрешимость этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.