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