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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «= Неразрешимость универсального языка = {{Утверждение |id=proposalU. |statement=[[Разрешимые (рекурс...»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
= Неразрешимость универсального языка =
 
{{Утверждение
 
|id=proposalU.
 
|statement=[[Разрешимые (рекурсивные) языки#Пример неразрешимого множества | Универсальный язык]] неразрешим
 
|proof=
 
Допустим, что он разрешим. Тогда напишем такую программу:
 
<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>, значит, пара не принадлежит. Опять получили противоречие.
 
}}
 

Текущая версия на 19:32, 4 сентября 2022