Изменения
Нет описания правки
{{Определение
|definition = '''Полусистема Туэ ''' (англ. ''semi-Thue system)''' ) {{---}} это формальная система, определяемая алфавитом <tex>A</tex>
и конечным множеством подстановок вида <tex>\alpha_i\rightarrow \beta_i</tex>, где <tex>\alpha_i, \beta_i</tex> - слова из <tex>A</tex>.
}}
|id=th1
|statement=
В полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (англ. ''word problem for semi-Thue systems'') неразрешима.
|proof=
Сведем (прим. [[m-сводимость]]) неразрешимую задачу проблемы останова (прим. приведена в примере использования [[Теорема_о_рекурсии|теоремы о рекурсии]]) к нашей. Для этого построим по структуре данной из проблемы останова МТ (прим. [[Машина Тьюринга]]) полусистему Туэ. Пусть <tex> q_1 </tex> {{---}} стартовое состояние, <tex> q_n </tex> {{---}} допускающее состояние МТ. Для построение искомой полусистемы будем описывать текущее состояние МТ с помощью строки <tex> \langle xqy\rangle </tex> , где <tex> q </tex> {{---}} текущее состояние автомата, <tex> xy </tex> {{---}} строка, записанная на ленте, <tex> \langle</tex> и <tex>\rangle </tex> {{---}} маркера начала и конца строки соответственно. Пусть <tex> s </tex> {{---}} последний символ строки <tex> x </tex>, а <tex> t </tex> {{---}} первый символ строки <tex> y </tex>. При этом головка указывает на символ <tex> t </tex>. Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
