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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 33 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition =  
+
|definition = '''Полусистема Туэ''' ('''ассоциативное исчисление''') (англ. ''semi-Thue system'') {{---}} это формальная система, определяемая алфавитом <tex>A</tex>
'''Полусистема Туэ(система подстановок)''' - это формальная система, определяемая алфавитом <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>\alpha_i, \beta_i</tex> - слова, возможно, пустые, в <tex>A</tex>.  
 
 
}}
 
}}
  
 
Подстановка <tex>\alpha_i\rightarrow \beta_i</tex> интерпретируется как правило вывода <tex>R_i</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>\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>\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> некоторой подстановкой.
  
<tex>\delta</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\rangle </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 \\
 +
sq't'      & \text{if } \downarrow \\
 +
st'q'      & \text{if } \rightarrow
 +
  \end{cases}
 +
</tex>
 +
 
 +
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркеров (прим. B {{---}} пустой символ ленты) :
  
{{Определение
+
<tex>q \rangle \rightarrow qB \rangle </tex> и <tex>\langle q \rightarrow \langle Bq </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>  
|definition =
 
'''Система Туэ(ассоциативное исчисление)''' - это формальная система, определяемая алфавитом <tex>A</tex>
 
и конечным множеством соотношений вида  <tex>\alpha_i\leftrightarrow \beta_i</tex>, которые понимаются как пара левой и правой подстановки, где  <tex>\alpha_i, \beta_i</tex> - слова, возможно, пустые, в <tex>A</tex>.
 
}}
 
  
Таким образом, ассоциативное исчисление всегда есть система подстановок.
+
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли  построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. При этом пусть это уникальное состоит лишь из символа допускающего состояния <tex> q_n </tex>. Таким образом, имеем следующие правила:
  
Полусистеме и системе Туэ можно поставить в соответствие машину Тьюринга.
+
<tex>q_n c \rightarrow  q_n </tex> и <tex>c q_n \rightarrow  q_n </tex> для <tex> \forall c \in T \cup Q \cup \{B,  \langle, \rangle \}  </tex>
  
Пусть <tex>A_T</tex> - алфавит машины Тьюринга, тогда <tex>A_S = A_T\cup \{ q_1, ... q_z\}</tex>
+
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* q_n </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>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
+
== См. также ==
}}
+
* [[m-сводимость]]
 +
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]
 +
* [[Примеры неразрешимых задач: задача о замощении | Задача о замощении]]
 +
* [[Неразрешимость исчисления предикатов первого порядка]]
 +
 
 +
==Примечания==
 +
<references/>
 +
 
 +
== Источники информации==
 +
* [[wikipedia:Semi-Thue_system | Wikipedia {{---}} Semi-Thue system]]
 +
*[http://problem24.wordpress.com/2011/07/07/lecture-on-undecidability-7-the-word-problem-for-thue-systems Undecidability of the word problem for semi-Thue systems ]
  
== Источники ==
+
[[Категория: Теория формальных языков]]
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера
+
[[Категория: Теория вычислимости]]

Текущая версия на 00:34, 3 июня 2018

Определение:
Полусистема Туэ (ассоциативное исчисление) (англ. semi-Thue system) — это формальная система, определяемая алфавитом [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 \ldots \vdash\beta[/math], где каждое [math]\epsilon_j[/math] получается из [math]\epsilon_{j-1}[/math] некоторой подстановкой.

Теорема:
В полусистеме Туэ задача вывода из слова [math]\alpha [/math] слово [math] \beta[/math] (англ. word problem for semi-Thue systems) неразрешима.
Доказательство:
[math]\triangleright[/math]

Сведем неразрешимую задачу проблемы останова[1] к нашей. Для этого построим по структуре данной из проблемы останова МТ полусистему Туэ. Пусть [math] q_1 [/math] — стартовое состояние, [math] q_n [/math] — допускающее состояние МТ. Для построение искомой полусистемы будем описывать текущее состояние МТ с помощью строки [math] \langle xqy\rangle [/math] , где [math] q [/math] — текущее состояние автомата, [math] xy [/math] — строка, записанная на ленте, [math] \langle[/math] и [math]\rangle [/math] — маркера начала и конца строки соответственно. Пусть [math] s [/math] — последний символ строки [math] x [/math], а [math] t [/math] — первый символ строки [math] y [/math]. При этом головка указывает на символ [math] t [/math]. Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:

[math] sqt \rightarrow \begin{cases} q'st' & \text{if } \leftarrow \\ sq't' & \text{if } \downarrow \\ st'q' & \text{if } \rightarrow \end{cases} [/math]

В силу конечности множеств состояний автомата ([math] Q [/math]) и алфавита ([math] T [/math]) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркеров (прим. B — пустой символ ленты) :

[math]q \rangle \rightarrow qB \rangle [/math] и [math]\langle q \rightarrow \langle Bq [/math] для [math] \forall q \in Q \setminus \{q_n\}[/math]

И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние [math] q_n [/math], получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. При этом пусть это уникальное состоит лишь из символа допускающего состояния [math] q_n [/math]. Таким образом, имеем следующие правила:

[math]q_n c \rightarrow q_n [/math] и [math]c q_n \rightarrow q_n [/math] для [math] \forall c \in T \cup Q \cup \{B, \langle, \rangle \} [/math]

Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове [math] u [/math], если в построенной полусистеме [math] \langle q_1u \rangle \vDash ^* q_n [/math]. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
[math]\triangleleft[/math]

См. также[править]

Примечания[править]

  1. Пример использования теоремы о рекурсии

Источники информации[править]