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=
<tex>
</tex>
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex>маркеров (прим. B {{---}} пустой символ ленты) :
<tex>q| \rangle \rightarrow q0| qB \rangle </tex> и <tex>|\langle q \rightarrow |0q \langle Bq </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем При этом пусть это уникальное состоит лишь из символа допускающего состояния <tex> q_n </tex>. Таким образом, имеем следующие правила:
<tex>q_nt q_n c \rightarrow q_n </tex> и <tex>c q_n \rightarrow q_n </tex> для <tex> \forall c \in T \cup Q \cup \{B, \langle, \rangle \} </tex>
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex>u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* q_n| \rightarrow 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 ]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]