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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «= Неразрешимость универсального языка = {{Утверждение |id=proposalU. |statement=[[Разрешимые (рекурс...»)
 
(Неразрешимость универсального языка)
Строка 1: Строка 1:
= Неразрешимость универсального языка =
 
 
{{Утверждение
 
{{Утверждение
 
|id=proposalU.  
 
|id=proposalU.  

Версия 23:52, 17 декабря 2016

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