確率論（もう一つの歴史的役割）

判断する予測すると言う行動も「計算」と言ってよいなら、情報圧縮も誤り検出・訂正もまた確率論に多くを負っている。

キーワード：アルゴリズム　チョムスキーの句構造文法　ランダムアクセスマシン　プログラム内蔵方式ＲＡＭ　ヒルベルトのプログラム　ゲーデルの不完全性定理　ゲーデル氏等の計算可能関数（帰納的関数・定義可能関数・ポスト正規システム等）　情報源符号化定理・通信路符号化定理　情報エントロピー　マルコフ情報源　平均符号長

参考

「チューリングの計算理論入門」　　　　　高岡詠子　著

「シャノンの情報理論入門」　　　　　　　高岡詠子　著