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