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

Материал из Викиконспекты
Версия от 23:52, 17 декабря 2016; ExileHell (обсуждение | вклад) (Новая страница: «= Неразрешимость универсального языка = {{Утверждение |id=proposalU. |statement=[[Разрешимые (рекурс...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Утверждение:
[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]