Изменения

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

Если Пусть язык <tex> u(p, x) = 1 U</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 \neq rangle) = 1 </tex>, то мы пойдём во вторую ветку условного оператора условие <tex>\mathrm{if}</tex> выполнится и вернём программа зависнет, но, так как программа <tex> 1 u </tex>разрешает универсальный язык, значит<tex> u(\langle r, пара r \rangle) = 1 \Rightarrow r(r) = 1</tex> ;* Eсли <tex> u(\langle pr, x r \rangle ) = 0 </tex>, то условие <tex>\mathrm{if}</tex> не выполнится и программа вернет <tex>1</tex> принадлежит универсальному языку, но , так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(p\langle r, xr \rangle) = 0 \Rightarrow r(r) \neq ne 1 </tex>, значит, пара не принадлежит. Опять получили противоречие Из предположения о разрешимости универсального языка мы пришли к противоречию.