313
правок
Изменения
→Доказательство
}}
====Доказательство====
Пусть <tex>KS(x)</tex> вычислима. Возьмем вместо <tex>f(x)\ KS(x)</tex>. Очевидно, что <tex>KS\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>.
