Изменения
Нет описания правки
==Определения==
===Декомпрессор===
{{Определение
|definition=
}}
==Свойства==
===Тривиальные свойства===
* <tex>KS(x) \leqslant |x| + c</tex>
* <tex>KS(x,y) \leqslant KS(x) + KS(y) + 2\lceil log_2 KS(x) \rceil + 2</tex>
Докажем последнее свойство:
===Невычислимость===
{{Лемма
|statement=
Если <tex>f:\{0,1\}^* \rightarrow N</tex> {{---}} вычислимая функция.
|proof=
}}
== Источники ==
