Примеры неразрешимых задач: задача о выводе в полусистеме Туэ

Определение:

Полусистема Туэ (система подстановок) - это формальная система, определяемая алфавитом [math]A[/math] и конечным множеством подстановок вида [math]\alpha_i\rightarrow \beta_i[/math], где [math]\alpha_i, \beta_i[/math] - слова из [math]A[/math].

Подстановка [math]\alpha_i\rightarrow \beta_i[/math] интерпретируется как правило вывода [math]R_i[/math] следующим образом: [math]\gamma \vDash \delta[/math] по [math]R_i[/math] , если слово [math]\delta[/math] получается путем подстановки какого-нибудь [math]\beta_i[/math] вместо какого-то вхождения [math]\alpha_i[/math] в [math]\gamma[/math].

Вывод [math]\beta[/math] из [math]\alpha[/math] - цепочка [math]\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash .. \vdash\beta[/math], где каждое [math]\epsilon_j[/math] получается из [math]\epsilon_{j-1}[/math] некоторой подстановкой.

[math]\delta[/math] заключительное, если оно выводимо в системе и к нему неприменима ни одна из подстановок.

Определение:

Система Туэ (ассоциативное исчисление) - это формальная система, определяемая алфавитом [math]A[/math] и конечным множеством соотношений вида [math]\alpha_i\leftrightarrow \beta_i[/math], которые понимаются как пара левой и правой подстановки, где [math]\alpha_i, \beta_i[/math] - слова, возможно, пустые, в [math]A[/math].

Таким образом, ассоциативное исчисление всегда есть система подстановок.

Полусистеме и системе Туэ можно поставить в соответствие машину Тьюринга.

Пусть [math]A_T[/math] - алфавит машины Тьюринга, тогда [math]A_S = A_T\cup \{ q_1, ... q_z\}[/math] Системе команд соответствует система соотношений [math]q_ia_i \rightarrow q_ia_lR[/math]; [math]q_ia_j \rightarrow a_lq_k[/math]; [math]q_ia_i \rightarrow q_ka_lL[/math]; [math]a_iq_ia_j \leftrightarrow q_ka_ta_l[/math] для любого [math] a_t \in A_T [/math]

Теорема:

В исчислении [math]S(T)[/math] слова [math]\alpha q_i a_j \beta \Leftrightarrow \gamma q_z a_k \delta[/math] тогда и только тогда, когда машина [math]T[/math] из конфигурации [math]\alpha q_i a_j \beta [/math] переходит в конфигурацию [math]\gamma q_za_k\delta[/math] за конечное число тактов.(1)

Теорема (Маркова-Поста):

Существует ассоциативное исчисление, в котором проблема распознования эквивалентности слов алгоритмически неразрешима.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Источники

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера