以下のQA記事がなかなか興味深かったのでご紹介します。

■圧縮すると容量が増える
http://soudan1.biglobe.ne.jp/qa5233484.html

既にエンコード済みのメディア形式のファイルをzipなどで圧縮すると、逆にファイルサイズが増えることがあります。
これは、どういうことかということを考えるとなかなか奥が深いわけですね。

ある一定のデータの複雑性を示す指標として、コルモゴロフ複雑性というものがあって、つきつめていくと複雑性を求める計算方法がないということのようです。
これは、チューリングの停止問題やゲーデルの不完全性定理とも通じるところがありますね。

これは、可逆圧縮のアルゴリズムにも言える事で、ありとあらゆるデータについてそのデータよりも小さいサイズでの表現に置き換えが可能かは、原理的に不可能という話なのですね。
http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%AB%E3%83%A2%E3%82%B4%E3%83%AD%E3%83%95%E8%A4%87%E9%9B%91%E6%80%A7#.E3.83.87.E3.83.BC.E3.82.BF.E5.9C.A7.E7.B8.AE.E3.81.AE.E9.99.90.E7.95.8C

システム開発において業務ロジックを設計するにあたり、普段はここまでのことを考える必要はありませんが、プログラミング言語と計算機科学はとても密接に関係していて、どういう理論の上になりたっているのかを考えるのはとても大切なことだと思いますね。