Изменения
Нет описания правки
Нетрудно заметить, что <tex>2|p| + 2</tex> зависит только от <tex>D</tex>, но никак не зависит от <tex>x</tex>, т.е. является константой. <br>
Следовательно, <tex>U</tex> {{---}} оптимальный декомпрессор.
}}
{{Определение
|definition=
Пусть <tex>D</tex> {{---}} это оптимальный декомпрессор, тогда '''колмогоровская сложность''' <tex>KS(x) = K_D(x)</tex>.
}}
{{Утверждение
|statement= Очевидно, что если <tex>D_1</tex> и <tex>D_2</tex> {{---}} оптимальные декомпрессоры, то <tex>\exists c_1, c_2: \forall x:
\left\{
\begin{array}{l l}
K_{D_1}(x) \leqslant K_{D_2}(x) + c_1 \\
K_{D_2}(x) \leqslant K_{D_1}(x) + c_2
\end{array}
\right.
</tex>
}}
