3622
правки
Изменения
псевдокод успенского-райса
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы. Далее будем считать, что такая функция определена в каждой программе.
== Неразрешимость универсального языка ==
{{Утверждение
<code>
p(x):
'''if''' u(pgetSrc(), x) // можем так написать, потому что по теореме о рекурсии программа может знать свой код
'''while''' ''true''
'''else'''
<tex> L_A </tex> {{---}} множество программ, удовлетворяющих св-ву <tex> A </tex>.
<code>
propA(code):
// программа, разрешающее свойство языка <tex> A </tex>
f(x):
// такая программа <tex> f </tex>, что <tex>f \in A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
g(x):
// такая программа <tex> g </tex>, что <tex>g \notin A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
p(x):
'''if''' p <tex> \in ~ L_A </tex> // можем так написать, потому что по предположению <tex> L_A </tex> {{---}} разрешимыйpropA(getSrc()) '''return''' qg(x)
'''else'''
</code>
Если <tex> p </tex> не удовлетворяет свойству <tex> A </tex>, тогда будет выполняться всегда вторая ветка, и <tex> L(p \equiv \varnothing ) = L(f) </tex>. Но пустой язык программы <tex> f </tex> принадлежит <tex> A </tex>. Получили противоречие.
Если <tex> p </tex> удовлетворяет свойству <tex> A </tex>, то <tex> L(p) = L(qg) </tex>, а <tex> q g \notin A </tex>. Опять получили противоречие.
== Колмогоровская сложность ==
{{Определение
