748
правок
Изменения
Нет описания правки
{{Определение
|definition = '''Полусистема Туэ ''' ('''ассоциативное исчисление''') (англ. ''semi-Thue system)''' ) {{--- }} это формальная система, определяемая алфавитом <tex>A</tex>и конечным множеством подстановок вида <tex>\alpha_i\rightarrow \beta_i</tex>, где <tex>\alpha_i, \beta_i</tex> - — слова из <tex>A</tex>.
}}
Подстановка <tex>\alpha_i\rightarrow \beta_i</tex> интерпретируется как правило вывода <tex>R_i</tex> следующим образом:
<tex>\gamma \vDash \delta</tex> по <tex>R_i</tex> , если слово <tex>\delta</tex> получается путем подстановки какого-нибудь <tex>\beta_i</tex> вместо какого-то вхождения <tex>\alpha_i</tex> в <tex>\gamma</tex>.
Вывод <tex>\beta</tex> из <tex>\alpha</tex> - — цепочка <tex>\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash .. \ldots \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой. {{Определение|definition = '''Проблема останова (halting problem)''' - это задача, в которой требуется по заданной программе проверить завершиться ли она на определенных входных данных.}}
{{Теорема
|id=th1
|statement=
|proof=
[[m-сводимость|Сведем]] неразрешимую задачу проблемы останова<ref>Пример использования [[Теорема_о_рекурсии|теоремы о рекурсии]]</ref> к нашей. Для этого построим по структуре данной из проблемы останова [[Машина Тьюринга|МТ]] полусистему Туэ. Пусть <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>. Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
<tex>
sqt \rightarrow
\begin{cases}
q'st' & \text{if } \leftarrow \\
sq't' & \text{if } \downarrow \\
st'q' & \text{if } \rightarrow
\end{cases}
</tex>
}}