Изменения
→Пример использования
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы. Далее будем считать, что такая функция определена в каждой программе.
== Неразрешимость универсального языка ==
{{Утверждение
|id=proposalU.
|statement=[[Разрешимые (рекурсивные) языки#Пример неразрешимого множества | Универсальный язык ]] неразрешим
|proof=
<code>
p(x):
'''if''' u(pgetSrc(), x) // можем так написать, потому что по теореме о рекурсии программа может знать свой код '''returnwhile''' ''true'' 0
'''else'''
'''return''' 1
</code>
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> возвращает должна вернуть <tex> 1 </tex>, но по условию <tex> if </tex> она должна вернуть <tex>0</tex>зависает, а следовательно, не принадлежит универсальному языку.
Если же <tex> u(p, x) = 0 \neq 1 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex> <\langle p, x> \rangle </tex> принадлежит универсальному языку, но <tex> u(p, x) = 0 \neq 1 </tex>, значит, пара не принадлежит. Опять получили противоречие.
}}
<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>. Опять получили противоречие.
== Колмогоровская сложность ==
{{Определение
|id=proposalU.
|statement=Функция [[Busy beaver]] невычислима.
|proof= Предположим, что это не так. Тогда напишем такую программу
<code>
p():
'''for''' i = 1..BB(p<tex>|\mathrm{getSrc()}|</tex>) + 1
do smth
</code>
Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(|p|) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.
}}
== Аналог I теоремы Гёделя о неполноте ==
{{Теорема
Можно переформулировать теорему следующим образом: невозможно доказать, что <tex> p(x) = \perp </tex>.
<code>
p(x):
</code>
}}
== Теорема о неподвижной точке ==
Зафиксируем [[Главные нумерации | главную нумерацию ]] <tex> W </tex>. Обозначим за <tex> W_n </tex> множество слов, допускаемых программой с номером <tex> n </tex>.
{{Утверждение
|id=идентификатор (необязательно), пример: proposalF.
<code>
p(q):
'''if''' p .getSrc() == q // сравниваем как строки; так можно сделать, потому что программа знает свой код по теореме о рекурсии.getSrc() print number(p)'''return''' 1
'''else'''
'''while''' ''true''
* [[wikipedia:Kolmogorov_complexity | Wikipedia {{---}} Kolmogorov_complexity]]
* [http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf Kolmogorov Complexity]
* [http://www.lektorium.tv/lecture/?id=13494 Дмитрий Ицыксон {{---}} Вычислимость и логика, Колмогоровская сложность]
[[Категория: Теория формальных языков]]
