Изменения

Докажем последнее свойство:

===Невычислимость===

|statement=

Если <tex>f:\{0,1\}^* \rightarrow N</tex> {{---}} [[Вычислимые функции|вычислимая функция]], такая, что <tex>\forall x : f(x) \leqslant KS(x)</tex>, тогда <tex>f = O(1)</tex>.