Вывод <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 =
'''Система Туэ Проблема останова (ассоциативное исчислениеhalting problem)''' - это формальная система, определяемая алфавитом <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</tex>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешимапримере использования [[Теорема_о_рекурсии|теоремы о рекурсии]].
}}
== Источники ==
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера
