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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = '''Полусистема Туэ''' ('''ассоциативное исчисление''') (англ. ''semi-Thue system'') {{---}} это формальная система, определяемая алфавитом <tex>A</tex>
+
|definition =  
и конечным множеством подстановок вида  <tex>\alpha_i\rightarrow \beta_i</tex>, где  <tex>\alpha_i, \beta_i</tex> слова из <tex>A</tex>.  
+
'''Полусистема Туэ (semi-Thue system)''' - это формальная система, определяемая алфавитом <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 \ldots \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 .. \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой.
 +
 
 +
{{Определение
 +
|definition =
 +
'''Проблема останова (halting problem)''' - это задача, в которой требуется по заданной программе проверить завершиться ли она на определенных входных данных.
 +
}}
  
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 
|statement=  
 
|statement=  
   В полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (англ. ''word problem for semi-Thue systems'') неразрешима.
+
   Проблема останова неразрешима.
 
|proof=
 
|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 {{---}} пустой символ ленты) :
+
{{Теорема
 +
|id=th2
 +
|statement=
 +
  В заданной полусистеме Туэ задача вывода из слова <tex>\alpha </tex> слово <tex> \beta</tex> (word problem for semi-Thue systems) неразрешима.
 +
|proof=
  
<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>. Таким образом, имеем следующие правила:
 
 
<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> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^*  q_n </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 ]
 
 
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: