Изменения
→Свойства
}}
==Свойства==
* <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>
* Если <tex>A</tex> {{---}} алгоритм, то <tex>KS(A(x)) \leqslant KS(x) + c_A</tex> <br> (<tex>A(x)</tex> запишем как пару {{---}} информация об алгоритме <tex>A</tex> и информация о строке <tex>x</tex>, по предыдущему пункту нам нужно закодировать только сложность первого аргумента, что есть константа)
* '''Принцип несжимаемости:''' <tex>\exists x \in \{0,1\}^n : KS(x) \geqslant n</tex> <br> (Какой бы у нас ни был архиватор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем <tex>n</tex> {{---}} <tex>(2^n-1)</tex>, мы не сможем деархивировать)
* <tex>KS</tex> {{---}} невычислимая функция.
Докажем последнее свойство:
== Источники ==
