Изменения
→Примеры
{{Теорема
|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 ... \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>.
Покажем, что такой декомпрессор будет лучше любого другого. <br> Пусть <tex>D</tex> {{---}} другой декомпрессор. По определению <tex>D</tex> {{---}} это алгоритм, значит есть программа, которая исполняет <tex>D</tex>. <br>
