チャイティンのΩとバエズのエントロピー
【「チャイティンのΩとバエズのエントロピー」を公開しました】 https://youtu.be/ZjMfjlBxO5o?list=PLQIrJ0f9gMcPPgVvBB4BWA7-RuBmWLqqz スライドのpdfはこちらです。 https://drive.google.com/file/d/1E545s0CYATo5NlFHlgMr-87SRfpIjwng/view?usp=sharing 今回から、バエズのエントロピーの話を始めようと思います。といっても、今回は、バエズのエントロピーの式が、先日話したチャイティンが定義した不思議な数Ωの定義によく似ているという話で終わります。 以前、「チャイティンとゲーデル」という小咄をことが書いたあります。冗談が好きな人は、こちらを参照ください。 https://maruyama097.blogspot.com/2017/01/blog-post_25.html 今回は、シャノンのエントロピーとコルモゴロフの複雑性について、いくつか基本的なことを確認したいと思います。 シャノンの理論は、 複数のオブジェクトの集まりをどのようにエンコードし、そうしたオブジェクトのシークエンスを如何に効率的に送るかについて考えます。それに対して、コルモゴロフの複雑性は、一つのオブジェクトを、最も効率的にエンコードすることを考えます。 ただ、「情報圧縮」という点では、二つの理論は共通の関心があります。 シャノンの理論では、例えば、アルファベットの集まりXがある確率分布に従う時、そのエントロピーH(X)を用いて、N文字のメッセージを。NH(X)ビットに情報圧縮できることを示せます。 コルモゴロフの複雑性理論では、次のような形で情報圧縮に関心を持ちます。 「Berryのパラドックス」というのがあります。 「30文字以下では定義されない最小の自然数B」 これはある意味、Bの定義ですが、Bは日本語では21文字で定義されています。 こうした「定義」「名前づけ」「記述」の曖昧さを避けるために、あるオブジェクトの「記述」はそれを出力するプログラムで与えられると考えます。コルモゴロフの複雑性𝐶_𝑈 (𝑥)は、万能チューリングマシンUにプログラムpが与えられた時、xを出力するプログラムpのうち、最小のプログラムの長さ(|p|)です。その時、pは、オブジェク