再掲「チャイティンのΩとバエズのエントロピー」

【「チャイティンのΩとバエズのエントロピー」】

今回から、バエズのエントロピーの話を始めようと思います。といっても、今回は、バエズのエントロピーの式が、先日話したチャイティンが定義した不思議な数Ωの定義によく似ているという話で終わります。

今回は、シャノンのエントロピーとコルモゴロフの複雑性について、いくつか基本的なことを確認したいと思います。

シャノンの理論は、複数のオブジェクトの集まりをどのようにエンコードし、そうしたオブジェクトのシークエンスを如何に効率的に送るかについて考えます。それに対して、コルモゴロフの複雑性は、一つのオブジェクトを、最も効率的にエンコードすることを考えます。

ただ、「情報圧縮」という点では、二つの理論は共通の関心があります。

シャノンの理論では、例えば、アルファベットの集まりXがある確率分布に従う時、そのエントロピーH(X)を用いて、N文字のメッセージを。NH(X)ビットに情報圧縮できることを示せます。

コルモゴロフの複雑性理論では、次のような形で情報圧縮に関心を持ちます。

「Berryのパラドックス」というのがあります。

　「30文字以下では定義されない最小の自然数B」

これはある意味、Bの定義ですが、Bは日本語では21文字で定義されています。

こうした「定義」「名前づけ」「記述」の曖昧さを避けるために、あるオブジェクトの「記述」はそれを出力するプログラムで与えられると考えます。

コルモゴロフの複雑性𝐶_𝑈 (𝑥)は、万能チューリングマシンUにプログラムpが与えられた時、xを出力するプログラムpのうち、最小のプログラムの長さ（|p|）です。その時、pは、オブジェクトの最小の記述を与えていると考えることができます。

こうした考えが威力を発揮するのは、あるビット列の「ランダムさ」を定義しようとする時です。

あるオブジェクトが、それより短い記述を持たない時、そのオブジェクトを「圧縮不可能」ということにしましょう。あるビット列が「ランダム」だと判断されるのは、それが「圧縮不可能」な時であると考えることができます。

Per Martin-Lofは、 1966年の論文“The Definition of Random Sequences” で、はじめて「ランダムさ」の定義を与えることに成功します。

残念なことに、チャイティンのΩについては、ほとんど説明できませんでした。

以前、「チャイティンとゲーデル」という小咄をことが書いたあります。冗談が好きな人は、こちらを参照ください。https://maruyama097.blogspot.com/2017/01/blog-post_25.html

「チャイティンの不完全性定理」をAgenda https://maruyama097.blogspot.com/2021/09/agenda-93.html に追加しました。（前回のマルレクで利用できなかったものです。）こちらから video, slide, blogにアクセスできます。

　● 第二部　計算可能性理論とコロモゴロフの複雑性

エピソード 3-4 「チャイティンの不完全性定理」 (video slide blog)

過去・現在・未来