Изменения
Нет описания правки
|definition=
Будем говорить, что декомпрессор <tex>D_1</tex> '''лучше''', чем декомпрессор <tex>D_2</tex>, если <tex>\exists c:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c</tex>.
}}
{{Теорема
|statement = Существует оптимальный декомпрессор <tex>U</tex>, который лучше всех остальных.
|proof = Пусть <tex>p</tex> {{---}} некоторая строка, <tex>|p| = n</tex>. Обозначим за <tex>\hat{p}</tex> строку <tex>p_1 p_1 p_2 p_2 ... 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>.
Покажем, что такой декомпрессор будет лучше любого другого. <br> Пусть <tex>D</tex> {{---}} другой декомпрессор. По определению <tex>D</tex> {{---}} это алгоритм, значит есть программа, которая исполняет <tex>D</tex>. <br>
<tex>p</tex> {{---}} номер алгоритма <tex>D,\ p = \#D</tex>. Тогда:<br>
<tex>K_U(x) \leqslant K_D(x) + 2|p| + 2</tex>, т.к. <tex>K_D(x)</tex> достигается на <tex>D(y) = U(\hat{p}y) = x</tex>, т.е. для этого <tex>y</tex> есть строка <tex>\hat{p}y</tex>, которая даёт тот же самый результат и имеет длину не больше, чем на <tex>2|p| + 2</tex>. <br>
Нетрудно заметить, что <tex>2|p| + 2</tex> зависит только от <tex>D</tex>, но никак не зависит от <tex>x</tex>, т.е. является константой. <br>
Следовательно, <tex>U</tex> {{---}} оптимальный декомпрессор.
}}
