Изменения
Архивация — это получение одного файла из нескольких; уменьшение — это сжатие!
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архивафайла, полученного сжатием строки каким-то конкретным архиватором компрессором (например, [[Алгоритм LZW|LZW]]). Но мы по-прежнему можем придумать строку, которая явно несет в себе мало информации, но которую архиватор компрессор тем не менее не сожмет.
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архивафайла, сжатого максимальным образом, самым лучшим архиваторомкомпрессором. Но тогда встает вопрос, почему такой архиватор компрессор существует. На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку.
==Определения==
* <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> {{---}} невычислимая функция.
