Изменения

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

Разрешимые (рекурсивные) языки

1096 байт убрано, 17:17, 2 января 2017
Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка
Если же <tex> u(p, x) \neq 1 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex>
\langle p, x \rangle </tex> принадлежит универсальному языку, но <tex> u(p, x) \neq 1 </tex>, значит, пара не принадлежит. Опять получили противоречие.
 
===Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка===
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>.
{{Лемма
|id=st2
|statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим.
|proof=
Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>.
Рассмотрим следущую программу:
<code>
<tex>p(x){:}</tex>
'''if''' <tex>r(p)</tex>
'''return''' 1
'''while''' true
</code>
Пусть <tex>p(\epsilon)=\perp</tex>. Тогда условие <tex>r(p)</tex> выполняется и <tex>p(\epsilon)=1</tex>. Противоречие. Если <tex>p(\epsilon) \ne \perp</tex>, то <tex>r(p)</tex> не выполняется и <tex>p(\epsilon)=\perp</tex>. Противоречие.
}}
== Примечания ==
313
правок

Навигация