14
правок
Изменения
Новая страница: «{{Определение |definition = '''Полусистема Туэ(система подстановок)''' - это формальная система, оп…»
{{Определение
|definition =
'''Полусистема Туэ(система подстановок)''' - это формальная система, определяемая алфавитом <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 .. \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой.
<tex>\delta</tex> заключительное, если оно выводимо в системе и к нему неприменима ни одна из подстановок.
{{Определение
|definition =
'''Система Туэ(ассоциативное исчисление)''' - это формальная система, определяемая алфавитом <tex>A</tex>
и конечным множеством соотношений вида <tex>\alpha_i\leftrightarrow \beta_i</tex>, которые понимаются как пара левой и правой подстановки, где <tex>\alpha_i, \beta_i</tex> - слова, возможно, пустые, в <tex>A</tex>.
}}
Таким образом, ассоциативное исчисление всегда есть система подстановок.
Полусистеме и системе Туэ можно поставить в соответствие машину Тьюринга.
Пусть <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=
|statement=
В исчислении <tex>S(T)</tex> слова <tex>\alpha q_i a_j \beta \Leftrightarrow \gamma q_z a_k \delta</tex> тогда и только тогда, когда машина <tex>T</tex> из конфигурации <tex>\alpha q_i a_j \beta </tex> переходит в конфигурацию <tex>\gamma q_za_k\delta</tex> за конечное число тактов.(1)
}}
{{Теорема
|id=th1
|about= Маркова-Поста
|statement=
Существует ассоциативное исчисление, в котором проблема распознования эквивалентности слов алгоритмически неразрешима.
|proof=
Возьмем какую-нибудь универсальную правильновычисляющую машину Тьюринга. Построим <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>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
}}
|definition =
'''Полусистема Туэ(система подстановок)''' - это формальная система, определяемая алфавитом <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 .. \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой.
<tex>\delta</tex> заключительное, если оно выводимо в системе и к нему неприменима ни одна из подстановок.
{{Определение
|definition =
'''Система Туэ(ассоциативное исчисление)''' - это формальная система, определяемая алфавитом <tex>A</tex>
и конечным множеством соотношений вида <tex>\alpha_i\leftrightarrow \beta_i</tex>, которые понимаются как пара левой и правой подстановки, где <tex>\alpha_i, \beta_i</tex> - слова, возможно, пустые, в <tex>A</tex>.
}}
Таким образом, ассоциативное исчисление всегда есть система подстановок.
Полусистеме и системе Туэ можно поставить в соответствие машину Тьюринга.
Пусть <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=
|statement=
В исчислении <tex>S(T)</tex> слова <tex>\alpha q_i a_j \beta \Leftrightarrow \gamma q_z a_k \delta</tex> тогда и только тогда, когда машина <tex>T</tex> из конфигурации <tex>\alpha q_i a_j \beta </tex> переходит в конфигурацию <tex>\gamma q_za_k\delta</tex> за конечное число тактов.(1)
}}
{{Теорема
|id=th1
|about= Маркова-Поста
|statement=
Существует ассоциативное исчисление, в котором проблема распознования эквивалентности слов алгоритмически неразрешима.
|proof=
Возьмем какую-нибудь универсальную правильновычисляющую машину Тьюринга. Построим <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>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
}}
