333
правки
Изменения
Нет описания правки
\end{cases}
</tex>
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex>:
<tex> tw \rightarrow w </tex> для <tex> \forall t \in T</tex>.
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> |q_0uq_1u| \vDash ^*|w| </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.}}
== Источники ==
* [[wikipedia:Semi-Thue_system | Wikipedia {{---}} Semi-Thue system]]
*[http://problem24.wordpress.com/2011/07/07/lecture-on-undecidability-7-the-word-problem-for-thue-systems Undecidability of the word problem for semi-Thue systems ]
