Изменения
→Невычислимость
{{Лемма
|statement=
Если <tex>f:\{0,1\}^* \rightarrow N</tex> {{---}} вычислимая функция, такая, что <tex>\forall x : f(x) \leqslant KS(x)</tex>, тогда <tex>f = O(1)</tex>.
|proof=
Пусть <tex>A(n) = \arg\min \limits_{x} f(x) \geqslant n</tex>, где <tex>n \in N</tex>, тогда <tex>A(n)</tex> {{---}} вычислимая (т.к <tex>f(x)</tex> {{---}} вычислима и ограничена), всюду определенная функция. <br>
По свойству невозрастания <tex>KS(x)</tex> при алгоритмических преобразованиях, <tex>KS(A(n)) \leqslant KS(n) + c_1 \leqslant log_2 n + c_2</tex>. <br> Вспомним, что <tex>f(x) \leqslant KS(x)</tex>, следовательно <tex>KS(A(n)) \geqslant f(A(n)) \geqslant n</tex>. <br> Отсюда: <tex>\forall n : log_2 n + c_2 \geqslant n</tex>, но ясно, что при больших <tex>n</tex> это неравенство не выполняется. Противоречие.
}}
<hr>
Примечание: если функция <tex>f(x)</tex> определена только на <tex>M \subset \{0,1\}^*</tex>, то лемма остается в силе с единственным отличием, что <tex>x</tex> пробегает все значения из <tex>M</tex> в порядке перечисления.
{{Утверждение
|about=следствие из леммы
|statement=
<tex>KS(x)</tex> невычислима.
|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> невычислима.
}}
== Источники ==
