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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 29: Строка 29:
 
   В полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (word problem for semi-Thue systems)  неразрешима.
 
   В полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (word problem for semi-Thue systems)  неразрешима.
 
|proof=
 
|proof=
Сведем (прим. [[m-сводимость]]) неразрешимую задачу проблемы останова к нашей. Для этого построим по структуре данной из проблемы останова МТ (прим. [[Машина Тьюринга]]) полусистему Туэ. Пусть <tex> q_1 </tex> {{---}} стартовое состояние, <tex> q_n </tex> {{---}} допускающее состояние МТ. Для построение искомой полусистемы будем описывать текущее состояние МТ с помощью строки <tex> |xqy| </tex> , где <tex> q </tex> {{---}} текущее состояние автомата, <tex> xy </tex> {{---}} строка, записанная на ленте. Пусть <tex> s </tex> {{---}} последний символ строки <tex> x </tex>, а <tex> t </tex> {{---}} первый символ строки <tex> y </tex>. При этом головка указывает на символ <tex> t </tex>.  Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
+
Сведем (прим. [[m-сводимость]]) неразрешимую задачу проблемы останова к нашей. Для этого построим по структуре данной из проблемы останова МТ (прим. [[Машина Тьюринга]]) полусистему Туэ. Пусть <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>
 
<tex>
Строка 40: Строка 40:
 
</tex>
 
</tex>
  
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex> (прим. B {{---}} пустой символ ленты) :
+
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркеров (прим. B {{---}} пустой символ ленты) :
  
<tex>q| \rightarrow qB| </tex> и <tex>|q \rightarrow |Bq </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>  
+
<tex>q \rangle \rightarrow qB \rangle </tex> и <tex>\langle q \rightarrow \langle Bq </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>  
  
 
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли  построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем следующие правила:
 
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли  построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем следующие правила:
Строка 48: Строка 48:
 
<tex>q_nt \rightarrow  q_n </tex>
 
<tex>q_nt \rightarrow  q_n </tex>
  
<tex>q_n| \rightarrow w| </tex>  
+
<tex>q_n \rangle \rightarrow w \rangle </tex>  
  
 
<tex> tw \rightarrow w </tex> для <tex> \forall t \in T</tex>.
 
<tex> tw \rightarrow w </tex> для <tex> \forall t \in T</tex>.
  
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> |q_1u| \vDash ^*|w| </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
+
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* \langle w \rangle </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
 
}}
 
}}
  

Версия 14:09, 18 января 2014

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


Определение:
Проблема останова (halting problem) — задача, в которой требуется по заданной программе проверить завершиться ли она на определенных входных данных.


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

Сведем (прим. m-сводимость) неразрешимую задачу проблемы останова к нашей. Для этого построим по структуре данной из проблемы останова МТ (прим. Машина Тьюринга) полусистему Туэ. Пусть [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_nt \rightarrow q_n [/math]

[math]q_n \rangle \rightarrow w \rangle [/math]

[math] tw \rightarrow w [/math] для [math] \forall t \in T[/math].

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

Источники