Изменения
Нет описания правки
'''Колмогоровскую сложность ''' (англ. ''Kolmogorov complexity)''' ) можно рассматривать как способ измерения количества информации в строке.
Но как понять, какое ''количество информации'' содержит в себе строка? Один из классических способов {{---}} это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
{{Определение
|definition=
Назовём '''декомпрессором''' (англ. ''decompressor'') <tex>D : \{0, 1\}^* \to
\left[\begin{array}{l}\{0, 1\}^* \\
\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.
{{Теорема
|statement = Существует '''оптимальный декомпрессор''' (англ. ''optimal decompressor'') <tex>U</tex>, который лучше всех остальных.
|proof = Пусть <tex>p</tex> {{---}} некоторая строка, <tex>|p| = n</tex>. Обозначим за <tex>\hat{p}</tex> строку <tex>p_1 p_1 p_2 p_2 \dots p_n p_n 0 1</tex> (мы удвоили каждый бит строки <tex>p</tex> и добавили в конце <tex>01</tex>).<br>
Оптимальный декомпрессор будет работать следующим образом: <tex>U(\hat{p}x) = \langle p \rangle(x)</tex>, т.е. он интерпретирует <tex>p</tex> как программу, а <tex>x</tex> как входные данные и запускает <tex>p</tex> на входе <tex>x</tex>.
