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