Изменения

Приведём доказательство от противногоПо [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код.Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.Допустим, что он разрешим. Тогда напишем такую программу:<code> p(x): '''if''' u(getSrc(), x) '''while''' ''true'' '''else''' '''return''' 1</code>

Пусть язык Если <tex>Uu(p, x) = 1 </tex> разрешим, тогда существует программа <tex> p </tex> на входе <tex> x </tex> должна вернуть <tex> 1 </tex>, но по условию <tex> if </tex> она зависает, а следовательно, не принадлежит универсальному языку.

Если же <tex>u(\langle p, x \rangle) = \begin{cases}1, \ \langle p, x \rangle \in U \\0, \ \langle p, x \rangle \notin U\end{cases}</tex>  Составим следующую программу:  <tex>r(x) {:} </tex> '''if''' <tex>u(\langle x, x \rangle) == 1 </tex> '''while''' ''true'' '''else''' '''return''' 1 Рассмотрим вызов <tex> r(r) </tex>:* Eсли <tex> u(\langle r, r \rangle) = neq 1 </tex>, то условие <tex>\mathrm{if}</tex> выполнится мы пойдём во вторую ветку условного оператора и программа зависнет, но, так как программа вернём <tex> u 1 </tex> разрешает универсальный язык, <tex> u(\langle rзначит, r \rangle) = 1 \Rightarrow r(r) = 1пара </tex>;* Eсли <tex> u(\langle rp, r x \rangle) = 0 </tex>, то условие <tex>\mathrm{if}</tex> не выполнится и программа вернет <tex>1</tex>принадлежит универсальному языку, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle rp, r \rangle) = 0 \Rightarrow r(rx) \ne neq 1</tex>, значит, пара не принадлежит. Из предположения о разрешимости универсального языка мы пришли к противоречиюОпять получили противоречие.