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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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> |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> |xqy| </tex> , где <tex> q </tex> {{---}} текущее состояние автомата, <tex> xy </tex> {{---}} строка, записанная на ленте. Пусть <tex> s </tex> {{---}} последний символ строки <tex> x </tex>, а <tex> t </tex> {{---}} строки <tex> y </tex>. При этом головка указывает на символ <tex> t </tex>.  Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
 +
 
 +
 
 
}}
 
}}
 
== Источники ==
 
== Источники ==
 
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера
 
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера

Версия 00:35, 14 января 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] |xqy| [/math] , где [math] q [/math] — текущее состояние автомата, [math] xy [/math] — строка, записанная на ленте. Пусть [math] s [/math] — последний символ строки [math] x [/math], а [math] t [/math] — строки [math] y [/math]. При этом головка указывает на символ [math] t [/math]. Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
[math]\triangleleft[/math]

Источники

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