313
правок
Изменения
→Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка
Рассмотрим следущую программу:
<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>. Противоречие.
