Изменения

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

Допустим, что он язык разрешим. Тогда напишем такую программу:  <codetex> p(x){:}</tex> '''if''' <tex>u(\mathrm{getSrc()}, x)</tex>

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