313
правок
Изменения
→Альтернативное доказательство
<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> вычислима, тогда напишем такую программу:
