3622
правки
Изменения
неразрешимость универсального языка
== Неразрешимость универсального языка ==
Считаем, что язык программ над тем же алфавитом, что и язык входных данных. Если это не так, то можно просто взять объединение алфавитов, это ничто не испортит.
Универсальная программа: <tex> u(p, x) = p(x) </tex>.
Универсальный язык: <tex> L_u = \{ <p, x> \mid u(p, x) = 1 \} </tex>
{{Утверждение
|id=proposalU.
|statement=Универсальный язык неразрешим
|proof=
Напишем такую программу:
<code>
p(x):
'''if''' u(p, x) // можем так написать, потому что по теореме о рекурсии программа может знать свой код
'''return''' 0
'''else'''
'''return''' 1
</code>
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> возвращает <tex> 1 </tex>, но по условию <tex> if </tex> она должна вернуть 0, а следовательно, не принадлежит универсальному языку.
Если же <tex> u(p, x) = 0 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex> <p, x> </tex> принадлежит универсальному языку, но <tex> u(p, x) = 0 </tex>, значит, пара не принадлежит. Опять получили противоречие.
}}
== Теорема Успенского-Райса ==
== Колмогоровская сложность ==
