Изменения

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

Участник:Shersh/Теорема о рекурсии

925 байт убрано, 23:56, 2 января 2017
Пример использования
</code>
Программа <tex> p </tex> знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число {{---}} свой номер.
}}
 
==Пример использования==
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p|p(\epsilon)=\perp\}</tex>.
{{Лемма
|id=st2
|statement= Язык <tex>L=\{p|p(\epsilon)=\perp\}</tex> неразрешим.
|proof=
Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>.
Рассмотрим следущую программу:
<code>
p(x)
if r(p)
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>. Противоречие.
}}
Анонимный участник

Навигация