任意の n ビットの列を n - 1 ビット以下の列に圧縮するアルゴリズムは存在しない
まじかんと雑記さんが僕のトラックバックに反応してくれて，とてもうれしい限りです．嬉しくて嬉しくて調子乗ってコメントしてきました！！！
では、次のようなプログラムを考えよう:
- プログラムへの入力
- 任意の有限ビット列 X
- プログラムの出力
- 特定の乱数生成器が出力乱数列としてビット列 X (で始まるビット列) を出力するような、乱数の種
このようなプログラムがあれば、元のデータそのものをやり取りしなくても、そのデータを作り出す元になる種を伝えるだけでよくなる。種を受け取った人は、乱数生成器にその種を入力すれば元のデータを復元できる。
これはただの乱数の種です - 「データ」と「情報」の狭間: まじかんと雑記
こういう話に明るくない方々が勘違いして恥をかかないように，ネタにマジレスして正しいことを引用しておきます．
任意の n ビットのファイルを n - 1 ビット以下に可逆に圧縮するアルゴリズムは存在しない。 ［証明］ n ビットのファイルは 2n 通り存在するが，n - 1 ビット以下のファイルは 1 + 2 + 22 + 23 + …… + 2n-1 = 2n - 1 通りしか存在しない。Shannon (1948): A Mathematical Theory of Communication
m 個の文字がそれぞれ出現確率 p1, p2, …, pm で独立に現れるとすると，平均して Σ pi log2 (1 / pi) ビット／文字より縮めることはできない。圧縮と詐欺 - データ圧縮技術の基礎と最近の動向
ということで，任意のデータを一個の乱数種と乱数発生アルゴリズムに分離するアルゴリズムは，現実的なプログラムでは実現できません．
