693
правки
Изменения
м
→Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка
}}
==Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка==
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>.
{{Лемма
|statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим.
|proof=
Предположим обратное, тогда . Тогда существует программа <tex>r</tex> разрещающая , разрешающая <tex>L</tex>.Рассмотрим следущую следующую программу:
<code>
<tex>p(x){:}</tex>
