333
правки
Изменения
Нет описания правки
<tex>
sqt \vDashrightarrow
\begin{cases}
q'st' & \text{if } \leftarrow \\
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex>:
<tex>q| \vDash rightarrow q0| </tex> и <tex>|q \vDash rightarrow |0q </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это позволит нам построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем следующие правила:
<tex>q_nt \vDash rightarrow q_n </tex>
<tex>q_n| \vDash rightarrow w| </tex>
<tex> tw \vDash rightarrow w </tex> для <tex> \forall t \in T</tex>.
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме из слова <tex> |q_0u| </tex> выводится <tex> \vDash ^*|w| </tex>. Таким образом из разрешимость разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
