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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 29: Строка 29:
 
<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 \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 </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли  построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. При этом пусть это уникальное слово имеет вид <tex> \langle w \rangle </tex>, где <tex> w \notin T </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>q_n c \rightarrow  q_n </tex> для <tex> \forall c \in T</tex>
  
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* q_n </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
+
<tex>q_n \rangle \rightarrow w \rangle </tex>
 +
 
 +
<tex> c w \rightarrow w </tex> для <tex> \forall c \in T</tex>.
 +
 
 +
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* \langle w \rangle </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
 
}}
 
}}
  

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

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

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

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