セクシーな夢、数学からみたランダム性
数学で言う不完全性定理、ゲーテル、チューリング、チャイティンの3名の名前が挙がる。
セクシーな数学―ゲーデルから芸術・科学まで
1930年ゲーテルの不完全性定理
形式公理的数学理論では解が存在しない場合がある。例としては嘘つきのパラドックスとして知られたものである。
「私は嘘つきである」が真なら、それは偽だということになり、偽ならばその内容は真ということになり正誤の判断ができない。同様に「私は嘘つきでない」が偽なら、それは真ということになり、真ならば内容から偽ということになり同様に正誤の判断ができない。(wiki)
チューリングのコンピュータ停止問題
チューリングは「コンピュータの機械言語は原始的だけれども、とても柔軟な汎用機械である事を明らかにします。(中略)この様な機械に何が不可能なのかとたずねます。何ができないのか。そして彼は、どのチューリングマシーンも解決できない問題を、即座にみつけます。それが、停止問題、チューリングマシーン、すなわコンピュータプログラムが最終的に停止するかどうかを前もって決定する問題です。」(184ページ)
私は、円周率の計算でイメージした。円周率をコンピュータで計算させて十分長い時間をかけても終わらず、終わるか終わらないか、判らない。そしてそれはプログラムで表現できない、そこにはランダム性があるから、と整理して理解をした。
チャイティンの数学のランダム性
チャイティンは数学にもランダム性がある事を証明した。先程の円周率の計算の例えは経験的であるが、それをより自然数学的な表現にしたと考える。
「私はプログラムサイズ計算機を使ってランダム性を定義するという新しいアイデアを思いつきました。そして、コンピュータプログラムのサイズを調べ始めると、実行時間計算量の代わりにプログラムサイズ、すなわち情報計算量という概念を考え始めると、不完全性が発見される様になりました。」(198ページ)
私は画像の圧縮でイメージした。例えばあるデータをZIPで圧縮するとそれが最大効率の圧縮方法と誰も断言できない。そもそもZIPには何種類もあるし同じプログラムを使っても結果は毎回違う事はまま経験する。チャイティンの言葉を借りれば「コンピュータプログラムが、私の言い方ではエレガント、すなわち、同じ出力を生成するものの中でもっとも簡潔なものであると確かめられないのです。」(199ページ
チャイティンは物理学で経験的に知られた不確実性は絶対と思われる自然数学ですら不完全性が存在する事を認識させた。
蛇足
ランダム性、これがあるから夢がある、「明日があるさ!」
