Изменения
Нет описания правки
В заданной полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (word problem for semi-Thue systems) неразрешима.
|proof=
Сведем (прим. [[m-сводимость]]) неразрешимую задачу проблемы останова к нашей. Для этого построим по структуре данной из проблемы останова МТ (прим. [[Машина Тьюринга]]) полусистему Туэ. Для этого будем описывать текущее состояние МТ с помощью строки <tex> |xqy| </tex> , где <tex> q </tex> {{---}} текущее состояние автомата, <tex> xy </tex> {{---}} строка, записанная на ленте. Пусть <tex> s </tex> {{---}} последний символ строки <tex> x </tex>, а <tex> t </tex> {{---}} строки <tex> y </tex>. При этом головка указывает на символ <tex> t </tex>. Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
}}
== Источники ==
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера
