Изменения

Перейти к: навигация, поиск

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

1283 байта добавлено, 23:52, 17 декабря 2016
Новая страница: «= Неразрешимость универсального языка = {{Утверждение |id=proposalU. |statement=[[Разрешимые (рекурс...»
= Неразрешимость универсального языка =
{{Утверждение
|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>, значит, пара не принадлежит. Опять получили противоречие.
}}
313
правок

Навигация