Изменения

|definition = '''Полусистема Туэ''' (система подстановок'''ассоциативное исчисление''')(англ. ''semi-Thue system'' ) {{- --}} это формальная система, определяемая алфавитом <tex>A</tex>и конечным множеством подстановок вида <tex>\alpha_i\rightarrow \beta_i</tex>, где <tex>\alpha_i, \beta_i</tex> - — слова, возможно, пустые, в из <tex>A</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> некоторой подстановкой.

{{Теорема|id=th1|statement= В полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (англ. ''word problem for semi-Thue systems'') неразрешима.|proof=[[m-сводимость|Сведем]] неразрешимую задачу проблемы останова<ref>Пример использования [[Теорема_о_рекурсии|теоремы о рекурсии]]</ref> к нашей. Для этого построим по структуре данной из проблемы останова [[Машина Тьюринга|МТ]] полусистему Туэ. Пусть <tex> q_1 </tex> {{---}} стартовое состояние, <tex>q_n </tex> {{---}} допускающее состояние МТ. Для построение искомой полусистемы будем описывать текущее состояние МТ с помощью строки <tex> \langle xqy\deltarangle </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 \\ |definition = sq't' & \text{if } \downarrow \\ st'q''Система Туэ & \text{if } \rightarrow \end{cases}</tex> В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (ассоциативное исчислениепредставленные выше)''' в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркеров (прим. B {{--- это формальная система, определяемая алфавитом }} пустой символ ленты) : <tex>Aq \rangle \rightarrow qB \rangle </tex>и конечным множеством соотношений вида <tex>\alpha_ilangle q \rightarrow \langle Bq </tex> для <tex> \forall q \leftrightarrow in Q \beta_isetminus \{q_n\}</tex> И наконец добавим в наш набор те правила, которые понимаются как пара левой и правой подстановкипозволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. При этом пусть это уникальное состоит лишь из символа допускающего состояния <tex> q_n </tex>. Таким образом, где имеем следующие правила: <tex>q_n c \alpha_i, rightarrow q_n </tex> и <tex>c q_n \beta_irightarrow q_n </tex> - словадля <tex> \forall c \in T \cup Q \cup \{B, возможно \langle, пустые\rangle \} </tex> Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex>A\langle q_1u \rangle \vDash ^* q_n </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.

Таким образом, ассоциативное исчисление всегда есть система подстановок== См.также ==* [[m-сводимость]]* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]* [[Примеры неразрешимых задач: задача о замощении | Задача о замощении]]* [[Неразрешимость исчисления предикатов первого порядка]]

Пусть <tex>A_T</tex> - алфавит машины Тьюринга, тогда <tex>A_S = A_T\cup \{ q_1, ... q_z\}</tex>Системе команд соответствует система соотношений<tex>q_ia_i \rightarrow q_ia_lR</tex>; <tex>q_ia_j \rightarrow a_lq_k</tex>; <tex>q_ia_i \rightarrow q_ka_lL</tex>; <tex>a_iq_ia_j \leftrightarrow q_ka_ta_l</tex> для любого <tex> a_t \in A_T </tex>{{Теорема|id=th1|aboutИсточники информации==* [[wikipedia:Semi-Thue_system |statement=Wikipedia {{---}} Semi-Thue system]] В исчислении <tex>S(T)<*[http:/tex> слова <tex>\alpha q_i a_j \beta \Leftrightarrow \gamma q_z a_k \delta</tex> тогда и только тогда, когда машина <tex>T<problem24.wordpress.com/tex> из конфигурации <tex>\alpha q_i a_j \beta <2011/tex> переходит в конфигурацию <tex>\gamma q_za_k\delta<07/tex> за конечное число тактов.(1)}}{{Теорема|id=th1|about= Маркова07/lecture-on-undecidability-7-the-word-problem-for-thue-systems Undecidability of the word problem for semi-Поста|statement= Существует ассоциативное исчисление, в котором проблема распознования эквивалентности слов алгоритмически неразрешима.|proof=Thue systems ]

Возьмем какую-нибудь универсальную правильновычисляющую машину Тьюринга. Построим <tex>S(U)</tex> и присоединим к нему <tex>q_za_i \leftrightarrow q_z</tex>, чем получим S'(U). В такой системе тоже можно имитировать исчислительный процесс <tex>U</tex>, как и в <tex>S(U)</tex>. Однако благодаря новым соотношениям все заключительные конфигурации <tex>U</tex> в <tex>S'(U)</tex> эквивалентны <tex>q_z</tex>. Поэтому для <tex>S'(U)</tex> (1) принимает вид[[Категория: в <tex>S'(U)</tex> слова <tex>q_1\alpha</tex> и <tex>q_z</tex> эквивалентны тогда и только тогда, когда <tex>U</tex>, начав с <tex>q_1\alpha q_z</tex>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.Теория формальных языков]]}}[[Категория: Теория вычислимости]]