333
правки
Изменения
Нет описания правки
В заданной полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (word problem for semi-Thue systems) неразрешима.
|proof=
Сведем (прим. [[m-сводимость]]) неразрешимую задачу проблемы останова к нашей. Для этого построим по структуре данной из проблемы останова МТ (прим. [[Машина Тьюринга]]) полусистему Туэ. Пусть <tex> q_1 </tex> {{---}} стартовое состояние, <tex> q_n </tex> {{---}} допускающее состояние МТ. Для этого построение искомой полусистемы будем описывать текущее состояние МТ с помощью строки <tex> |xqy| </tex> , где <tex> q </tex> {{---}} текущее состояние автомата, <tex> xy </tex> {{---}} строка, записанная на ленте. Пусть <tex> s </tex> {{---}} последний символ строки <tex> x </tex>, а <tex> t </tex> {{---}} строки <tex> y </tex>. При этом головка указывает на символ <tex> t </tex>. Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
<tex>
</tex>
}}
В силу конечности множеств состояний автомата и алфавита добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex>:
<tex>q| \rightarrow q0| </tex> <tex> \forall q \in Q \setminus \{q_n\}</tex>
<tex>|q \rightarrow |0q </tex> <tex> \forall q \in Q \setminus \{q_n\}</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 ]
