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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = '''Полусистема Туэ(система подстановок)''' - это формальная система, оп…»)
 
Строка 41: Строка 41:
 
Возьмем какую-нибудь универсальную правильновычисляющую машину Тьюринга. Построим <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>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
 
Возьмем какую-нибудь универсальную правильновычисляющую машину Тьюринга. Построим <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>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
 
}}
 
}}
 +
 +
== Источники ==
 +
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера

Версия 08:10, 16 января 2011

Определение:
Полусистема Туэ(система подстановок) - это формальная система, определяемая алфавитом [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 q_z[/math], остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
[math]\triangleleft[/math]

Источники

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