過去・現在・未来

【 アルゴリズム論的熱力学 】 https://youtu.be/n2O8H0UDhqE?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ここでは、John BaezとMike Stayの 2013年の論文 “Algorithmic Thermodynamics” を紹介します。https://arxiv.org/abs/1010.2067　 John Baez は、先に見た古典的な熱力学の観測量を、アルゴリズム論的情報理論の観測量で置き換えたモデルを考えました。 　　E(x)を、プログラムxの実行時間の対数 　　V(x)を、プログラムxの長さ 　　N(x)を、プログラムxの出力 とします。 この時、ある分配関数を考えて、確率分布 Gibbs Ensemble を構成します。 式については、pdfを参照ください。 https://drive.google.com/file/d/1rZY-ePmL9Ox1gPnkhL1fYFbO3kfjVXKx/view?usp=sharing これらから、観測量 E(x), V(x), N(x) の共役変数 𝛽,𝛾,𝛿を使って、期待値 E,V,Nを定義できます。 注意して欲しいのは、ここでの、E(x), V(x), N(x) の選択は、必然的なものではありません。ある意味、恣意的です。 用語については、まぎらわしいかもしれないですが、古典的な熱力学のGibbs Ensembleの例を流用しています。 重要なことは、、古典的な熱力学と同じ方法で、アルゴリズム論的熱力学が構成可能なことを示せるということです。それが、Gibbs Ensembleの方法の強みです。 また、計算時間、プログラムの長さ、プログラムの出力という観測量は、アルゴリズム論的情報理論にとっては、重要なものです。 さきには、「まぎらわしい」と言いましたが、次のように考えることもできます。 アルゴリズム論的熱力学のE、すなわち、計算時間の対数は、古典的熱力学のガスの内部エネルギーに似ている。 アルゴリズム論的熱力学のV、すなわち、プログラムの長さは、古典的熱力学の容器の体積に似ている。 アルゴリズム論的熱力学のN、すなわち、プログラムの出力は、古典的熱力学の分子の数に似ている。 はたして、こうしたアナロジーは、どこまで有効なものになる

【 Gibbs Ensemble と共役変数 】 https://youtu.be/xa845uRr8fY?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ここでは、"Gibbs Ensemble" と「共役変数」という二つの概念を導入します。 式が少し複雑になるので、次のpdfファイルをご利用ください。 https://drive.google.com/file/d/1GAOuC99EKwpGY6JV8Pokj1dEdXkayg0q/view?usp=sharing まず、古典的な熱力学の単純な例から。 次のような確率分布と分配関数Zが与えられているとします。Eはエネルギーです。 　　p(x) = 1/Z (e^{βE(x)}) 　　Z = Σ e^{βE(x)} こうした系は、"Gibbs Ensemble" で、βはエネルギーEの「共役変数」です。 この時、β = 1/T （逆温度）になるのは、以前、見てきました。 （マルゼミ「情報とエントロピー 」を参照ください https://www.marulabo.net/docs/info-entropy2/　） 次に、もう少し複雑な例を考えます。 ガスの分子からなるある系について、エネルギーEだけでなく、体積V、圧力P、ガスの分子数Nについても観測量の期待値が与えられているすると、観測量とその共役変数に次のような対応があることがわかります。 　　　　観測量　　　　　共役変数 　　エネルギー E　　　　　1/T 　　体積          V 　　　　　P/T 　　分子数　    N_i             −μ_i/T  ----------- ショートムービーのpdfファイルは、次から利用できます。 https://drive.google.com/file/d/1GAOuC99EKwpGY6JV8Pokj1dEdXkayg0q/view?usp=sharing セミナー「コロモゴロフ複雑性とアルゴリズム論的情報理」のまとめページは、こちらです。 https://www.marulabo.net/docs/info-entropy4/ セミナーのAgendaはこちらです。 https://maruyama097.blogspot.com/

【 アルゴリズム論的情報理論への分配関数Zの応用 】 https://youtu.be/9Jnjz2qQULs?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K 先に見たのは、系のエネルギーEが、各部分系に\(𝐸_𝑖\)として分配されているとして、エントロピーが最大になる条件を求めるものでした。 確率が、 $$p_i = \frac{1}{Z}e^{−βE_i } $$ で与えられる時、 分配関数Zは　 $$Z = \sum  e^{−βE_i } $$ になります。 先にプログラムxの確率を次のように定義しました。 $$q_x = \frac{1}{Z}e^{−V(x) } $$ 実は、プログラムの確率がこの形をしているという積極的な理由があるわけではありません。 ただ、次のような形を作れば、熱力学の手法が応用できるというのが、この形を選んだ一番大きな理由です。 　　\(p_x = \frac{1}{Z} e^{−γV(x) }  \) 　　\(Z = \sum e^{−γV(x) }  \) この\(𝑝_𝑥\) と𝑍に、次のような解釈を与えることができます。 プログラムの集合上の確率分布Pのエントロピーを最大にする条件を考えます。拘束条件が、プログラムの長さだとすれば、その答えは、次のようになります。 $$p_x = \frac{1}{Z} e^{−γV(x) } $$ ここで、次のZが、\(p_x\)の和が1となること、すなわち、 \(p_x\)が確率であることを保証します。 $$Z = \sum e^{−γV(x) } $$ 先の \(q_x\) は、\(𝛾 = ln⁡ 2\)  と置いたものです。 こうした、確率変数 \(p_x\) と分配関数Zの関係は、一般的なものです。 今まで、拘束条件として、EやVの期待値を一つだけとってきたのですが、複数の観測の期待値から、同じような導出が可能です。 $$p_x = \frac{1}{Z} e^{−βE(x)−γV(x)−δN(x) } $$ ここでは、次のZが、\(p_x\) の和が1となること、すなわち、 \(p_x\) が確率であることを保証します。 $$Z = \sum  e^{−βE(x)−γV(x)−δN(x) }   $$ ----------- ショートムー

【 分配関数 Z – 統計力学の方法を振り返る 】 https://youtu.be/li-BsDN9JBY?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K 前回、アルゴリズム論的情報量に確率の概念を導入することができて、そうするとシャノンの情報量との関係がわかってくるという話をしました。アルゴリズム論的情報量をある数Zで割ると、その総和が1となるような確率p_n が定義できるということでした。 今回は、そのZがどういうものかという話です。二つの見方を紹介します。 一つは、アルゴリズム論的情報理論的には、ここで導入されたZの値は、ある条件のもとでは、チャイティンのΩに等しくなります。これは、とても面白いことなのですが、今回は深入りしません。 もう一つは、このZは、統計力学的には分配関数と言われるものと同じ役割を果たしているということです。今回は、改めて、統計力学の方法を振り返ってみようと思います。 ある条件が与えられた時に、ある式が極値をもつが条件を考えようというアプローチです。熱力学的には、ある条件として系のエネルギーの平均値Eが与えられた時、エントロピーSが最大になる条件を考えていきます。   与えられた拘束条件を、C1 = 0 , C2 = 0 の形で表せば、 　　S = S + α・C1 + β・C2 と書き換えることができます。（後ろの二項はゼロですので） この時、エントロピーSが最大になる必要な条件は、上の式を何らかの変数で微分したとき、その値がゼロになることです。こうして、α、βが満たすべき条件を得ることができます。 具体的には、拘束条件 C1として「確率の和は1になる」、拘束条件 C2として「系のエネルギーの平均値はEである」という条件を利用します。 こうしたやり方を「ラグランジェの未定乗数法」というのですが、その中で、Zを導入します。Zの具体的な導出は、スライドのpdfをご覧ください。 https://drive.google.com/file/d/1n4UA2AvgX_C_g-z-w3t22wzqxy2sYu_l/view?usp=sharing 詳しくは、マルゼミ「情報とエントロピー」を参照ください。 https://www.marulabo.net/docs/info-entropy2/ ここでは、拘束条件は二

【 アルゴリズム論的情報量に確率の概念を導入する 】 https://youtu.be/x24csujO1Vk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K 前回は、アルゴリズム論的情報量の、見かけが異なる二つの定義が、同じものであることを見てきました。今回は、その結果を踏まえて、アルゴリズム論的情報量が、シャノンの情報量と等しいということを見ていきたいと思います。 まず、シャノン的情報量（information gain）とアルゴリズム論的情報量を比較してみましょう。いずれも − log⁡ 𝑋という形をしています。 ただ、 −log⁡ 𝑋のXの部分は、ずいぶん違っています。シャノン的情報量の場合のpは0≤𝑝≤1を満たす「確率」と定義されていますが、アルゴリズム論的情報量ではそうではありません。 アルゴリズム論的情報量には、確率の概念がかけています。そのままでは、アルゴリズム論的情報量と、シャノンの情報量の対応づけは難しいです。 ただ、うまい方法があります。 アルゴリズム論的情報量の対数の内側の量について、ある定数Zを選んで、次のような量𝑝_𝑛を定義します。 この時、p_nが確率であることを示すことができます。（ 0 ≤ p_n ≤ 1 、かつ Σ p_i = 1 ) 【 式は、Facebookやメールでは、表現しにくいものも多いので、次のスライドのodfをご覧ください。https://drive.google.com/file/d/1QPs2nqbZxWGhf1NRpM27YR5J3Jc4g9Vq/view?usp=sharing  】 p_nの定義から、次の式を導くことができます。 　　𝑆(𝑛) = − log⁡ p_n  − log⁡𝑍  これから、nのアルゴリズム論的情報量であるS(n)は、定数の差を除けば、−log⁡p_n  に等しいことがわかります。−log⁡ p_n は、シャノンのinformation gainの情報量です。 どんなinformation gain かと言えば、確率分布Pに従う自然数の集合から、ランダムに一つのnを選んだときに、得られる情報が、−log⁡ p_n です。 こうして、次のように、アルゴリズム論的情報量とシャノン的情報量の対応を考えることができます。 事前には、我々は、ある

【 二つのアルゴリズム論的情報量の関係 】 Xをプログラムの集合、𝑉(𝑥) をプログラムの長さ、𝑁(𝑥)をプログラムxの出力とすると、二つの情報量の定義は、次のようになります、 第一の定義 （コロモゴロフ複雑性） $$𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) = min_{𝑥∈𝑋}⁡ \{ 𝑉(𝑥) : 𝑁(𝑥)=𝑛 \}$$ 第二の定義 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛} 2^{−𝑉(𝑥) } $$ \(𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)と𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)\)の関係を考えてみましょう\( S(𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛}2^{−𝑉(𝑥) } \) で、nを出力とするようなプログラムxが一つしかなかったとしましょう。総和の項は一つしかないということです。 この時、 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑 }(𝑛) = − log⁡ 2^{−𝑉(𝑥)} = 𝑉(𝑥)$$ となります。 nを出力とするようなプログラムxが一つしかないというのですから、V(x)は、𝑁(𝑥)=𝑛 を満たすプログラムの最小の長さになります。この時、 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)=𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) $$  になります。 もちろん、nを出力するプログラムは、複数存在し得ます。この時、アルゴリズム論的情報量の第二の定義による、 \(𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)\)は、それらのプログラムの長さの項 \(− log⁡ 2^{−𝑉(𝑥)} \)が寄与しますので、その分、\(𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)\)より小さくなります。 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)≤ 𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)$$ 1974年に、Leonid Levinは、次のような定理を証明しました。すなわち、prefix free なプログラム言語については、すべてのnについて、次の式が成り立つような定数cが存在すると。 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛) ≥ 𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) − 𝑐$$ このこと

【アルゴリズム論的情報量】 https://youtu.be/UgDNZzXIBik?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ここでは、「アルゴリズム論的情報量」の定義を２つ与えます。 プログラム言語を固定します。ここで、プログラムは、有限のビット列で、プログラムが停止するなら、その出力も、有限のビット列です。 この時、ある有限なビット列の「アルゴリズム論的情報量」を、そのビット列を出力するプログラムの最小の長さで定義します。 この、ある自然数nの「アルゴリズム論的情報量」の第一の定義では、それが、nの「コロモゴロフ複雑性」に等しいと考えます。 「アルゴリズム論的情報量」＝「コロモゴロフ複雑性」を、通常の、シャノン情報理論での「情報量」＝「シャノン・エントロピー」とを比較してみましょう。 あるイベントxが確率pで起きたとしましょう。シャノンの情理論では、あるイベントxが起きたことを知った時に、「獲得した情報量」を、 　　−log ⁡𝑝 で表します。 “information gain” とか “information content”、“surprise” あるいは「自己情報量」といわれる情報量です。 ただ、シャノンの情報理論で、通常、「情報量」と言われるのは、X上の確率分布Pが与えられ、𝑥∈𝑋が確率𝑝_𝑥で起きる時、次の式で与えられる量です。 　　𝑆(𝑃 ) = −∑_(𝑥∈𝑋) 𝑝_𝑥  log ⁡𝑝_𝑥  これをシャノン・エントロピー と呼びます。 ただ、この「情報量」＝「エントロピー」は、先に見た「アルゴリズム論的情報量」と似ているようには見えませんね。 通常のシャノンの「情報量」との関係を、もっと分かりやすくするために、「アルゴリズム論的情報量」の二番目の定義を導入することにしましょう。 引き続き、プログラムは、有限のビット列だと考えます。もちろん、すべての有限のビット列が停止するプログラムを与えるわけではありません。  Xをプログラムのビット列の集合とする時、 𝑥∈𝑋なら任意のビット列yについて、𝑥𝑦∉𝑋とします。プログラム 𝑥で始まり、その後ろに𝑦をつなげた𝑥𝑦は、プログラムのビット列にはならないということです。 この条件を満たす時、Xをprefix free と言いま

【アルゴリズム論的情報量】 ここでは、「アルゴリズム論的情報量」の定義を２つ与えます。 https://youtu.be/UgDNZzXIBik?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K プログラム言語を固定します。ここで、プログラムは、有限のビット列で、プログラムが停止するなら、その出力も、有限のビット列です。 この時、ある有限なビット列の「アルゴリズム論的情報量」を、そのビット列を出力するプログラムの最小の長さで定義します。 この、ある自然数nの「アルゴリズム論的情報量」の第一の定義では、それが、nの「コロモゴロフ複雑性」に等しいと考えます。 「アルゴリズム論的情報量」＝「コロモゴロフ複雑性」を、通常の、シャノン情報理論での「情報量」＝「シャノン・エントロピー」とを比較してみましょう。 あるイベントxが確率pで起きたとしましょう。シャノンの情理論では、あるイベントxが起きたことを知った時に、「獲得した情報量」を、 $$−log  ⁡𝑝$$ で表します。 “information gain” とか “information content”、“surprise” あるいは「自己情報量」といわれる情報量です。 ただ、シャノンの情報理論で、通常、「情報量」と言われるのは、X上の確率分布Pが与えられ、\(𝑥∈𝑋が確率𝑝_𝑥\)で起きる時、次の式で与えられる量です。 $$𝑆(𝑃 ) = −\sum_{𝑥∈𝑋} 𝑝_𝑥  log  ⁡𝑝_𝑥 $$ これをシャノン・エントロピー と呼びます。 ただ、この「情報量」＝「エントロピー」は、先に見た「アルゴリズム論的情報量」と似ているようには見えませんね。 通常のシャノンの「情報量」との関係を、もっと分かりやすくするために、「アルゴリズム論的情報量」の二番目の定義を導入することにしましょう。 引き続き、プログラムは、有限のビット列だと考えます。もちろん、すべての有限のビット列が停止するプログラムを与えるわけではありません。  Xをプログラムのビット列の集合とする時、 𝑥∈𝑋なら任意のビット列yについて、𝑥𝑦∉𝑋とします。プログラム 𝑥で始まり、その後ろに𝑦をつなげた𝑥𝑦は、プログラムのビット列にはならないということです。 この条件を満たす時、Xをpre

【「チャイティンのΩとバエズのエントロピー」】 今回から、バエズのエントロピーの話を始めようと思います。といっても、今回は、バエズのエントロピーの式が、先日話したチャイティンが定義した不思議な数Ωの定義によく似ているという話で終わります。 https://youtu.be/ZjMfjlBxO5o?list=PLQIrJ0f9gMcPPgVvBB4BWA7-RuBmWLqqz 今回は、シャノンのエントロピーとコルモゴロフの複雑性について、いくつか基本的なことを確認したいと思います。 シャノンの理論は、 複数のオブジェクトの集まりをどのようにエンコードし、そうしたオブジェクトのシークエンスを如何に効率的に送るかについて考えます。それに対して、コルモゴロフの複雑性は、一つのオブジェクトを、最も効率的にエンコードすることを考えます。 ただ、「情報圧縮」という点では、二つの理論は共通の関心があります。 シャノンの理論では、例えば、アルファベットの集まりXがある確率分布に従う時、そのエントロピーH(X)を用いて、N文字のメッセージを。NH(X)ビットに情報圧縮できることを示せます。 コルモゴロフの複雑性理論では、次のような形で情報圧縮に関心を持ちます。 「Berryのパラドックス」というのがあります。 　「30文字以下では定義されない最小の自然数B」 これはある意味、Bの定義ですが、Bは日本語では21文字で定義されています。 こうした「定義」「名前づけ」「記述」の曖昧さを避けるために、あるオブジェクトの「記述」はそれを出力するプログラムで与えられると考えます。 コルモゴロフの複雑性𝐶_𝑈 (𝑥)は、万能チューリングマシンUにプログラムpが与えられた時、xを出力するプログラムpのうち、最小のプログラムの長さ（|p|）です。その時、pは、オブジェクトの最小の記述を与えていると考えることができます。 こうした考えが威力を発揮するのは、あるビット列の「ランダムさ」を定義しようとする時です。 あるオブジェクトが、それより短い記述を持たない時、そのオブジェクトを「圧縮不可能」ということにしましょう。あるビット列が「ランダム」だと判断されるのは、それが「圧縮不可能」な時であると考えることができます。 Per Martin-Lofは、 1966年の論文“The Definition o

「コロモゴロフ複雑性とアルゴリズム論的情報理論」 　Agenda 　 　● 第一部　ランダムさの不思議 エピソード 1 「ランダムさの不思議」( video   pdf    blog ) エピソード 2 「Randomness と Symmetry」 ( video   pdf   blog ) エピソード 3 「ランダムの力  — 量子論のインパクト」 ( video   pdf   blog )  エピソード 4 「ランダムさの定義の難しさ」 ( video   pdf   blog ) エピソード 5 「ランダムさ への新しいアプローチ」 ( video    pdf   blog ) 　● 第二部　計算可能性理論とコロモゴロフの複雑性 エピソード 0 「コロモゴロフの複雑性」( video   pdf   blog ) エピソード 1 「すべての計算可能な関数は、プログラムで表現できる」 ( video   pdf   blog ) エピソード 2 「コロモゴロフ複雑性の「不変性」」( video   pdf   blog ) エピソード 3 「コロモゴロフ複雑性の「計算不能性」」 ( video   pdf   blog ) エピソード 4 「チャイティンの不完全性定理」 ( video   slide   blog ) 　● 第三部　アルゴリズム論的情報理論 エピソード 4-1 「チャイティンのΩとバエズのエントロピー」 ( video pdf blog ) エピソード 4-2 「アルゴリズム論的情報量」 ( video pdf blog ) エピソード 4-3 「二つのアルゴリズム論的情報量の関係」 ( video pdf blog ) エピソード 4-4 「アルゴリズム論的情報量に確率の概念を導入する」( video pdf blog ) エピソード 4-5 「分配関数 Z – 統計力学の方法を振り返る」 ( video pdf blog )

【 お詫びとお知らせ：9/3 マルゼミのタイトルを変更します】 9/3マルゼミのタイトルを、「計算科学とエントロピー」から「コロモゴロフ複雑性とアルゴリズム論的情報理論」へと変更したいと思っています。 予告した基本的なコンテンツや、現在展開中のショートムービーは、そのまま引継ぎますが、今回のセミナーでは、コロモゴロフ複雑性とシャノンの情報理論のエントロピーとの接点をあまりお話しすることができません。今回は、タイトルから、「エントロピー」を消そうと思いました。 タイトル、「計算科学と情報理論」でも良かったのですが、すこし一般的すぎると思います。いっそ、今回中心的に取り上げることのできるトピックをタイトルにしようと考えました。 セミナーは、次の三部構成です。 　● 第一部　ランダムさの不思議 　● 第二部　計算可能性理論とコロモゴロフの複雑性 　● 第三部　アルゴリズム論的熱力学 今週から、第三部の「アルゴリズム論的熱力学」のショートムービーの展開を始めます。お楽しみに。 セミナーに向けた資料は、次のページにまとめられています。ご利用ください。 https://www.marulabo.net/docs/info-entropy4/ セミナーのお申し込みは、次のサイトからお願いします。 https://info-entropy4.peatix.com/view 　　　「コロモゴロフ複雑性とアルゴリズム論的情報理論」 　　　　　Agendaとショートムービー・リンクのリスト 　　　リンクにジャンプできる次のURLからご利用ください 　 https://maruyama097.blogspot.com/2021/09/agenda-93.html 　● 第一部　ランダムさの不思議 エピソード 2-1 「ランダムさの不思議」( video   pdf    blog ) エピソード 2-2 「Randomness と Symmetry」 ( video   pdf   blog ) エピソード 2-3 「ランダムの力  — 量子論のインパクト」 ( video   pdf   blog )  エピソード 2-4 「ランダムさの定義の難しさ」 ( video   pdf   blog ) エピソード 2-5 「ランダムさ への新しいアプローチ」 ( video    pdf  

【 コロモゴロフ複雑性の「計算不能性」】 https://youtu.be/Iir7Y9WNcZk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K コロモゴロフ複雑性には、重要な性質があります。 それは、コロモゴロフ複雑性は、xを出力するプログラムの最小の長さとして定義されるのですが、計算理論的には、それは「計算不能」です。 ここでは、そのことを見ていきましょう。 つぎのような関数Lを考えます。 　　𝐿(𝑛)=𝐾(𝑘)≥2𝑛 となるような最小の𝑘 関数 L : ℕ → 𝒪 は、nに対して、そのコロモゴロフ複雑性𝐾(𝑘)が2n 以上となるような最小の kを返します。もし、Kがすべてのnについて計算可能だとすると、Lもすべてのnについて計算可能です。 　　ここで、すべての𝑛に対して、𝐾(𝐿(𝑛))≥2𝑛 です。 なぜならば、すべての𝑛について、𝐿(𝑛)は、𝐾(𝐿(𝑛)) ≥ 2𝑛を満たす最小のものであるからです。 ここで、ある　V : 𝒪  → ℕ  が、「最適」であるとしましょう。この時、𝐾=𝐾_𝑉 と書くことができます。前回見た「不変性定理」から、𝐾 ≤ 𝐾_𝐿 + 𝑐 である定数cが存在することがわかります。   　　𝐾_𝐿 の定義から、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 が成り立ちます。 なぜならば、𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 } で、𝜑=𝐿として、 𝐾_𝐿 (𝐿(𝑛))=min⁡{ |𝑝|  :𝐿(𝑝)=𝐿(𝑛) }となります。 𝑝=𝑛 の場合、L(𝑝)=𝐿(𝑛)  が成り立つので、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 がいえます。 そうすると、次の不等式が成り立ちます。 　　2𝑛 ≤ 𝐾(𝐿(𝑛)) ≤ 𝐾_𝐿 (𝐿(𝑛)) + 𝑐 ≤ 𝑛 + 𝑐  　　2𝑛 ≤ 𝑛 + 𝑐 から 𝑛 ≤ 𝑐 ということになります。 ただし、この不等式は、全ての n については成り立ちません。𝑛 > 𝑐 なるnについては矛盾します。 Kがすべてのnについて計算可能だと仮定すると、矛盾が導かれるので、Kは計算可能ではありません。 ------------ このショ

【 ランダムさ への新しいアプローチ 】 https://youtu.be/Ks4iav2PR10?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ランダムさへのアプローチは、1960年代の半ばに、旧ソヴィエトの数学者コロモゴロフとその学派が登場して、新しい段階に入りました。 「コロモゴロフ複雑性」を中心的な武器とした「アルゴリズム論的情報理論」は、チャーチ＝チューリングらの計算理論との接点を深化し（Chaitinの「不完全性定理」)、また、シャノンの情報理論との結びつきを探求します(「条件付きエントロピー」、「相互エントロピー」)。 ここでは、まず、彼らのランダムさへのアプローチの概略を、次の三つのトピックで、紹介しようと思います。 　● 「オブジェクトの記述」＝「プログラム」 　● プログラムの長さへの注目 　● 圧縮可能な情報と圧縮不可能な情報 【「オブジェクトの記述」＝「プログラム」】 ある認識の対象を「記述」するには、いろいろな方法があります。 ・その定義を、記述する。 ・その特徴を、記述する。 ・その時間的変化を、記述する。 ・その意味を、記述する。 ・ … アルゴリズム論的情報理論では、少なくとも文字列として表現されるもの（それは、基本的には {0, 1}^∗ すなわち、0と1の並び　に還元されるのですが）、その「記述」とは、その文字列を出力する「プログラム」に等しいと考えます。 【 プログラムの長さへの注目 】 私たちの認識の対象は、多様です。対象の「記述」＝「プログラム」だとしても、ある対象を「記述」する「プログラム」も多様です。 一般的にいって、対象が複雑であれば、その「記述」、すなわちその対象を出力する「プログラム」も複雑なものになり、対象が単純なものであれば、その対象を出力する「プログラム」も単純なものになるのは、容易に想像できると思います。 プログラムの複雑さを、そのプログラムの「長さ」で代表させましょう。そうすることで、我々の認識の対象に、その複雑さを表す尺度を導入できます。 ある対象xを出力するプログラムは、複数あり得ます。この複数あるxを出力するプログラムで、最小の長さを持つものの長さを、xの「コロモゴロフ複雑性」と言います。 確認して欲しいのは、このように、xのコロモゴロフ複雑性は、一つの自然数だとい

【ランダムさの定義の難しさ】 「ランダムさ」を数学的に定義することは、実は、難しいのです。 確率論でも量子力学でも、「ランダムさ」は、もっとも基本的な概念の一つです。基本的な概念が数学的にうまく定義できないというのは、なにか奇妙なことのように思えるかもしれませんが、そういうことは、厳密な学と思われる思われる数学でも、よく起きることです。 例えば、幾何学では、「点」・「直線」・「図形」といった、最も基本的な概念は、うまく数学的に定義されている訳ではありません。集合論でも、「要素」・「集合」・「ある集合がある要素を含む」といった基本的な概念も、ある意味、天下り的に与えられます。 重要なことは、一つには、我々がそれらの概念についてある種の「直観」を持っていることと、もう一つには、それらの基本的な概念を、厳密ではなくとも、他のものとの関係で説明することができることです。 事実、確率論でも統計学でも量子論の解釈でも、「ランダムさ」を数学的にうまくは定義できなくても、それらの学は発展することが出来ました。ただ、いつまでもそれでいい訳ではありません。 数学的な認識の発展は、数学的認識の基礎に対する新しい反省を可能にします。「ランダムさ」についても、新しい数学的なアプローチが発見されます。 今回は、まず、「ランダムさの定義」の「失敗」を振り返ろうと思います。 19世紀のラプラスは、「ランダムさ」を次のように考えました。 　「ある数列は、規則性をほとんど含まないなら、ランダムである。」 これは、「規則的」でないものでランダムさを特徴づけようとするものです。 確かに、「0が100個続く数列は規則的である。」これはいいです。ただ、3.14159....と続くπ の並びは、規則的でしょうか？　あるいは、規則的でないものの例を、我々は具体的に示せるのでしょうか？ 20世紀に入って、フォン・ミーゼスは、フォン・ミーゼスは、数列無限Sの「ランダムさ」の定義として、次の二つの条件を提案しました。 　● Sの1項目からn項目までの部分列S_{1:n }での1の出現確率は、nが大きくなるにつれて一定の確率に近づく 　● ある関数によって選ばれた任意のSの部分列についても、その部分列での1の出現確率は、nが大きくなるにつれて一定の確率に近づく これは正しいでしょうか？ この「ランダムさ」の定義は、Sから

【 コロモゴロフ複雑性の「不変性」】 コロモゴロフ複雑性\(𝐾_𝜑 (𝑦)\)の定義： 「yを出力するプログラムpの最小の長さ」の問題の一つは、この\(𝐾_𝜑 (𝑦)\)が、プログラムを実行する𝜑に強く依存していることです。 　　　　　　\(𝐾_𝜑 (𝑦)\) = min ⁡{ |𝑝| : 𝜑(𝑝)=𝑦 }  事実、プログラムが Pythonで書かれているか、Javaで書かれているか、Assemblerで書かれているか, …. で、同じyを出力するプログラムの長さは、それぞれ違います。 ただ、任意の𝜑に対して、次の不等式を満たすVが存在することを示すことが出来ます。 $$𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$$ ここで、cは定数です。（証明は、後に回します） すべての𝜑に対して、この不等式を満たすVと定数cが存在することを、コロモゴロフ複雑性の「不変性定理」と呼びます。 この不等式を満たすVを「最適な」Vと呼ぶことにしましょう。   「不変性定理」は、 𝜑がいろいろ変わっても、\(𝐾_𝜑\) の(正確に言えば \(𝐾_𝜑 (𝑦) + 𝑐\) の)最小値𝐾_𝑉を与える 「最適な」Vが存在することを主張しています。 「不変性定理」で定義される「最適な」 V を使って、新しいコロモゴロフ複雑性 K(y)を次のように定義できます。 $$𝐾(𝑦)≡𝐾_𝑉 (𝑦)$$ この𝐾(𝑦)が、新しいコロモゴロフ複雑性の定義になります。 $$𝐾(𝑦)≡𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$$ ですので、𝐾(𝑦)は、\(𝐾_𝜑 (𝑦)\)たちの取る値の最小値です。 もし、𝑉と𝑉 'が共に「最適」であるなら、 $$|𝐾_𝑉 (𝑦) − 𝐾_{𝑉′'} (𝑦)| ≤ 𝑐$$ が成り立ちます。 コロモゴロフは、論文”Three approaches to the quantitative definition of information” 1965 の中でこの定数について、次のように述べています。 「もちろん、特定の関数Vを考えることで、この定数cに関連した非決定性を避けることはできる。しかし、あからさまな恣意性抜きに、そうしたことができるか

【「ランダムの力 -- 量子論のインパクト」を公開しました】 私たちのこころには、「秩序」「シンメトリー」を持つものを「美しい」と感ずる傾向があります。 こうした傾向は、芸術だけに見られるものでなく、物理学も、ある意味で「対称性」を追求します。 しかし、少なくとも、自然認識に関して言えば、20世紀の物理学は大きな転換に遭遇することになります。 それは、量子論が、自然の原理には、「ランダムさ」が深く組み込まれていることを発見したからです。 アインシュタインが「神はサイコロを振らない」といって、量子論を不完全な理論と見做したことはよく知られています。 ここでは、物理学者たちが、量子論の非決定論的性質、自然の「ランダムさ」を、どのように理解しようとしたかを見てみたいと思います。 興味深いのは、多くの物理学者が、人間の「認識」の能力との関係で、これらの問題を捉えようとしたことだと思います。 ウィグナーは、波動関数の崩壊は、意識との相互作用によるものだと提案します。 ダイソンは、「こころ」は選択をする能力によって特徴づけられるのだが、それは、ある程度は、全ての電子にも内在する性質であると論じます。 ボームは、物質と意識の双方に適用可能な秩序があると論じます。それによって、両者のあいだの関係が説明できるだろうと示唆します。 こころと物質は、より基本的な内的な秩序からの、外的な秩序への二つの反映だと考えます。 ペンローズは、「脳のどこか深いところで、一つの量子の変化を感じることのできる細胞が見つかるかもしれないと考えることができる。もしも、そうだということが証明されれば、量子力学は脳の活動に深く関わっていることになる。波動関数の崩壊は、人間の脳の非計算可能的なプロセスの、唯一の可能な物理的基礎となる。」と考えます。 コンウェーとコッヘンは、「量子の振る舞いの観測は、その量子の過去の振る舞いでは決定されない　オープンな結果を返す。このことは、量子が「自由意志」を持つと解釈できる」と。 はてさて、どうゆうことになるのやら。 ショートムービーお楽しみください。 https://youtu.be/GC-10IQ9zuc?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K スライドのpdfは、次からアクセスできます。 https://drive.google.c

【「Randomness と Symmetry」を公開しました 】 9/30 マルゼミ「計算科学とエントロピー」 https://info-entropy4.peatix.com/ にむけたショートムービー「Randomness と Symmetry」を公開しました。ご利用ください。 https://youtu.be/C3zeYLTDQDs?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K スライドのpdfは、こちらからアクセスできます。 https://drive.google.com/file/d/1ptC4hf9FVN9U998zE134yQIsofePphow/view?usp=sharing 「ランダムさ」の反対は、「秩序を持っていること」だと思います。 熱力学の第二法則「エントロピーの増大則」は、秩序を持っているものが、基本的には、時間の経過とともに「秩序・構造」を失い、最終的には「無秩序」で「ランダム」な状態になるという法則です。 「秩序を持っていること」の代表的なものが「対称性を持つこと」です。 鉱物の結晶は、対称性を持ちます。また、ほとんどの生き物は、正面から見て左右対象のからだを持っています。（コロナ・ウィルスでさえ、そうです。）あるルールに従って生成されるパターンも「対称性を持つ」と言うことがあります。 ここでは、「ランダムさ」の反対概念として、「対称性」という言葉を使っています。 自然に存在するもの（物質・生物）だけでなく、人間が作り出す多くのものも「対称性」を持っています。それは、我々が、「対称的なもの」に「美しさ」を感じるからだと考えられています。 「科学」も「数学」もまた、人間が作り出したものですが、今回は、詳しくは触れませんが、そこでも「対称性」の追求が、大きなドライビング・フォースになっています。 我々の目に止まるもの、我々の関心を引きつけるものの「中核」が、「美しく完璧な」対称性であるならば、その反対の極である「ランダムなもの」に関心を集中し、その特徴づけを目指すのは、難しいのです。 「ランダムなもの」は「美しく」ないし、「完璧なランダムさ」は形容矛盾で存在しません。 それにも関わらず、我々は「ランダムなものの」の「深淵」に取り囲まれています。

【「すべての計算可能な関数は プログラムで表現できる」を公開しました 】 9/30 マルゼミ「計算科学とエントロピー」 https://info-entropy4.peatix.com/ にむけたショートムービー「ランダムさの不思議」を公開しました。ご利用ください。 https://youtu.be/UplIfbz0Qsk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K スライドのpdfは、こちらからアクセスできます。 https://drive.google.com/file/d/1WoI4t4KPvUU39APaTjVddr5S9BPleeCO/view?usp=sharing ここでは、関数とプログラムの関係を、コロモゴロフの複雑性の定義から、考えようと思います。 コロモゴロフの複雑性は、「yを出力するプログラムpの最小の長さ」として、次のように定義されました。 　　𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 } この定義の中に出てくる関数の型を確認しておきましょう。プログラムのクラスを𝒫とし、プログラムの出力のクラスを𝒪としましょう。 　𝜑 : 𝒫 ⟶ 𝒪　 　　  /* 𝜑(𝑝)=𝑦 */ 　 　 /* 𝜑は、プログラム p : 𝒫を出力 y : 𝒪に変える関数 */   𝐾_𝜑  : 𝒪 ⟶ ℕ　     　　 /* 𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 } */ 　　 /* 𝐾_𝜑は、出力 y : 𝒪を自然数 ℕに変える関数 */ ここで、すこし天下り的ですが、「すべての計算可能な関数は、プログラムで表現できる」と考えることにしましょう。 計算可能な関数の値は、関数に対応するあるプログラムがあって、そのプログラムを実行して得られる出力に等しいということです。 こうした主張を、「チャーチ＝チューリングの提言」と言います。 「チャーチ＝チューリングの提言」は、基本的には、関数とプログラムは同じものであることを主張しているのですが、関数とプログラムでは、言葉の使い方が異なります。 　　関数の「引数」を、プログラムでは「入力」と言います。 　　関数の「値」を、プログラムでは「出力」と言います。 まあ、でもこの言い換えは、自然なものです

【「ランダムさの不思議」公開しました 】 9/30 マルゼミ「計算科学とエントロピー」 https://info-entropy4.peatix.com/ にむけたショートムービー「ランダムさの不思議」を公開しました。ご利用ください。 https://youtu.be/3V-AeDtR8Zs?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K スライドのpdfは、こちらからアクセスできます。 https://drive.google.com/file/d/1FzXttmm_FMEpqiSKf6XIHb7CeKObVo1Q/view?usp=sharing 「ランダムさ」に対して、我々はある種の直観を持っているように見えます。ただ、そうした直観が、必ずしも正確なものでないことを、次のような例で話そうと思います。 　・ランダムな0と1の並び 　・ランダムな文字列 「ランダムさ」というのは、実は、定義するのが難しい、不思議な性質を持っています。 ランダムな 0と１の並びを作ろうと思ったら、コインを投げて、表が出たら0、裏が出たら1とすればいいですね。そうして作られた並びは、きっとランダムなものに見えるでしょう。 ところで、もしも、0が30個並んでいる並びを見せられたら、それはランダムなものには見えないでしょう。 なぜでしょう？ 　「コインを投げて、30回連続して表が出ることは、確率的にあり得ないから」 ただ、確率的には、コイントスで得られる30桁の0,1の 並びは、全て同じ確率 \( (1/2)^{30} \) を持っています。みなに「ランダム認定」されるだろう 0,1の30桁の並びと、0が30個並ぶ並びとは、同じ確率で出現します。 確率だけでは、ランダムなものとそうでないものを区別することはできません。 ランダムな文字列を得るために、猿にタイプライターを叩かせましょう。 猿が打ち出す文字列は、ランダムと言えるでしょうか？ アルファベット（小文字）は、‘a’から‘z’まで26文字です。もしも猿が26キーのタイプライターを6回適当に叩いたとすると、この時、猿がうちだすことが可能な文字列の総数は、26の6乗で、308,915,776になります。9桁の数字で3億ちょっとです。 この中には、”monkey”という文字列が含まれています。“monke

 【「コロモゴロフの複雑性」を公開しました。】 9/30 マルゼミ「計算科学とエントロピー」 https://info-entropy4.peatix.com/ にむけたショートムービー「コロモゴロフの複雑性」を公開しました。ご利用ください。 https://youtu.be/X4jACH86kds?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K スライドのpdfは、こちらからアクセスできます。 https://drive.google.com/file/d/11KvGD40-SrPJA4wc-oaDDRvdvdTCzUk5/view?usp=sharing ある出力Xを与えるプログラムの長さの最小値を、Xの「コロモロゴフの複雑性」と言います。「アルゴリズム論的情報理論」の出発点は、この「コロモロゴフの複雑性」です。 なぜ、「プログラムの長さの最小値」かといえば、同じ結果を返すいくらでも冗長なプログラムはかけるのですから、出力の「複雑さ」をプログラムの「大きさ」に一意に対応づけようとするのなら、その結果を返す「最も短いプログラム」の大きさを考えるのがいいことになるからです。 コロモゴロフの複雑性を、もう少しきちんと定式化するために、プログラムとその出力の関係をどう表現すればいいかを考えて見ましょう。そこには、プログラムの「実行」という考えが必要です。 プログラム pの出力が yだとします。このことは、ある実行環境のもとでプログラム pを「実行」すれば、出力 y が得られるということです。このことを、次のように表しましょう。 $$ 𝜑(𝑝)=𝑦 $$ 𝜑は、「ある実行環境でのプログラムの実行」を表しています。 この時、ある実行環境𝜑のもとでのプログラム p の実行の出力 yのコロモゴロフの複雑性𝐾_𝜑 (𝑦)は、次のように定義できます。 $$ 𝐾_𝜑 (𝑦)=min⁡ \{ |𝑝| : 𝜑(𝑝)=𝑦 \} $$ここで、minは最小値、|p|は、プログラム p の長さを表しています。 少し、形式的に関数の型を整理しましょう。 プログラム pを、0と1の有限のビット列 {0,1}*とし、 プログラムの出力のクラスをOで表すと、 $$𝜑 : {0,1}^*⟶ O$$ $$𝐾_𝜑 : O ⟶ ℕ$$です。

【 9/30 マルゼミ「計算科学とエントロピー」のお誘い】 これまで、丸山のセミナーでは、エントロピーについて、主要に、ボルツマン・ギブスらの統計力学的アプローチと、シャノンの情報理論的アプローチの二つを見てきました。 今回のマルゼミ「計算科学とエントロピー」では、それら二つとは異なるエントロピーへのアプローチを取り上げます。「アルゴリズム論的情報理論 ("Algorithmic information theory")」といわれるものです。 「アルゴリズム論的情報理論」は、計算科学でのチューリングらの計算可能性の理論と、シャノンの情報理論とを結びつけようという試みです。 熱力学的エントロピーは、分子の運動の「乱雑さ」の尺度と考えられます。同じ「水」でも、水の分子が結晶上に規則的に並ぶ「氷」のエントロピーは低く、水の分子が自由に空中を飛び回る「水蒸気」のエントロピーは高くなります。 ビットの列で与えられる情報でも同じです。100個の"0"が連なるビット列は、規則的なのでエントロピーは低く、「ランダム」に、"0"と"1"が並ぶビット列は、エントロピーが高いと考えることができます。 ただ、この例え話は、実は、我々が何が「規則的」で何が「ランダム」かを判断できることを、暗黙のうちに仮定しています。「ランダムさ」でエントロピー を説明するのなら、「ランダムさ」とは何かを、きちんと説明できなければいけません。 あるビット列Xとビット列Yが与えられた時、次のように考えることにしましょう。 Xを出力するコンピュータ・プログラムの集まりをPX、Yを出力するコンピュータ・プログラムの集まりをPYとしましょう。（X,Yを出力するプログラムは一つとは限りません） ここで、「プログラムの長さ」を考えます。Xを出力するコンピュータ・プログラムの集まりPXに属する全てのプログラムについて、その「長さ」を考え、その中で一番短いものの長さをx とします。同様に、Yを出力するプログラムで一番短いものの長さをy とします。 この時、プログラムの長さ x, y を比較して、x < y なら、ビット列Yはビット列Xより「複雑」だと考えます。要するに、あるビット列を出力する最小のプログラムの長さが大きければ大きいほど、その