Неразрешимость универсального языка

Неразрешимость универсального языка

Утверждение:

Универсальный язык неразрешим

[math]\triangleright[/math]

Допустим, что он разрешим. Тогда напишем такую программу: p(x): if u(getSrc(), x) while true else return 1 Если [math] u(p, x) = 1 [/math], тогда программа [math] p [/math] на входе [math] x [/math] должна вернуть [math] 1 [/math], но по условию [math] if [/math] она зависает, а следовательно, не принадлежит универсальному языку. Если же [math] u(p, x) \neq 1 [/math], то мы пойдём во вторую ветку условного оператора и вернём [math] 1 [/math], значит, пара [math] \langle p, x \rangle [/math] принадлежит универсальному языку, но [math] u(p, x) \neq 1 [/math], значит, пара не принадлежит. Опять получили противоречие.

[math]\triangleleft[/math]