3622
правки
Изменения
универсальный язык: пофиксено доказательство
{{Утверждение
|id=proposalU.
|statement=[[Разрешимые (рекурсивные) языки#Пример неразрешимого множества | Универсальный язык ]] неразрешим
|proof=
Напишем такую программу:
p(x):
'''if''' u(p, x) // можем так написать, потому что по теореме о рекурсии программа может знать свой код
'''returnwhile''' 0''true''
'''else'''
'''return''' 1
</code>
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> возвращает должна вернуть <tex> 1 </tex>, но по условию <tex> if </tex> она должна вернуть <tex>0</tex>зависает, а следовательно, не принадлежит универсальному языку.
Если же <tex> u(p, x) = 0 \neq 1 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex> <\langle p, x> \rangle </tex> принадлежит универсальному языку, но <tex> u(p, x) = 0 \neq 1 </tex>, значит, пара не принадлежит. Опять получили противоречие.
}}
