1632
правки
Изменения
м
|proof=
Пусть <tex>KS(x)</tex> вычислима. Возьмем вместо <tex>f(x)\ KS(x)</tex>. Очевидно, что <tex>KS(x) \leqslant KS(x)</tex>, но из принципа несжимаемости ясно, что <tex>KS(x)</tex> неограничена. Противоречие. Следовательно, <tex>KS(x)</tex> невычислима.
rollbackEdits.php mass rollback
Докажем последнее свойство:
===Невычислимость===
{{Утверждение|about=Лемма
|statement=
Если <tex>f:\{0,1\}^* \rightarrow N</tex> {{---}} [[Вычислимые функции|вычислимая функция]], такая, что <tex>\forall x : f(x) \leqslant KS(x)</tex>, тогда <tex>f = O(1)</tex>.
|statement=
<tex>KS(x)</tex> невычислима.
}}
Пусть <tex>KS(x)</tex> вычислима. Возьмем вместо <tex>f(x)\ KS(x)</tex>. Очевидно, что <tex>\forall x : f(x) \leqslant KS(x)</tex>, но из принципа несжимаемости ясно, что <tex>KS(x)</tex> неограничена. Противоречие. Следовательно, <tex>KS(x)</tex> невычислима.
<tex> \forall x > x_0: K(x) > f(x)</tex>, если только <tex>f \leqslant const </tex> или <tex> f </tex> {{---}} невычислима.
====Альтернативное доказательство с использованием теоремы о рекурсии====
Функция <tex> K(x) </tex> {{---}} это минимальная длина программы <tex> p : p(\varepsilon) = x </tex>.
Допустим, что <tex> K </tex> вычислима, тогда напишем такую программу:
<code>
<tex>p(\varepsilon){:}</tex>
'''foreach''' <tex>x\in ~ \Sigma^* </tex> <span style="color:Green">//перебираем слова по возрастанию длины</span>
'''if''' <tex> K(x) > |p|</tex> <span style="color:Green">//теорема о рекурсии используется здесь</span>
'''return'''<tex>(x)</tex>
</code>
Длина этой программы меньше длины минимальной программы, которая возвращает <tex>x</tex> на пустом входе. Поэтому возникает противоречие. Следовательно <tex> K </tex> невычислима.
==Применение==
