アルゴリズム的情報理論について日本語で触れられている書物を，思い出せる範囲でまとめておきましょう．
日経サイエンス 2006年6月号
「ゲーデルを超えて オメガ数が示す数学の限界」
2006年なので，私が修士2年の時に読んだもの．
たぶん，この記事でランダムネスの理論を知った．
まずは，チャイティンの本
『数学の限界 』(2001)
『セクシーな数学―ゲーデルから芸術・科学まで』(2003)
『知の限界』(2006)
『メタマス!―オメガをめぐる数学の冒険』(2007)
やはり，こういう広報は重要だと感じる．
あと，ランダムの方向性から，触れられているものとして，
『ランダム―数学における偶然と秩序』ベルトラミ（2002)の第４章
情報の方向性から，
『インフォメーション: 情報技術の人類史』の第12章
数学的な解説としては，
渡辺治『計算論から見たランダムネス』(2006)
や
私の『ランダムネスの一般化』
などでしょうか．
他にもあったと思いますが，思い出したら，気がついたら，加えます．