思わぬところからチャイティンの停止確率Ωに関するテクストをもらう

ブログは書いてみるものだ。かつてチャイティンの本の話をブログに書いておいたら、それを見た方から、チャイティンの停止確率Ωを実証的に論じた短かいテクスト（A4 で 4 枚）をもらった。思わぬ収穫である。

実際に LISP 処理系で (omega 18) まで計算した結果を示していらっしゃる。(omega n) は「Ωの最初の n ビット」Ωn より小さいが、n → ∞ でΩに収束する性質がある LISP 関数である。
ああ、こういう楽しみ方があったんだなあ、と思った。

テクストでは書ききれなかった話題としていくつか挙げられているが、その中の「(omega n) の単調増加と最小上界」に興味を持った。ここまでお膳立てしてもらってあれば、自力でΩの最小上界を計算するプログラムを作れるのではないか、という気がしてきた*1。

それとは別に、私はチャイティンの停止確率がほぼ 1 に近いことを証明したいと思う。

• チャイティンは人間である。
• 現在の技術では人間はいつか死ぬ。そのとき停止する。
• 人間がいつまでも死なない技術が、チャイティンの寿命が来るまでに開発される確率βはべらぼうに小さい。
• 人間がいつまでも死なない技術があったとして、それをチャイティンが受け入れる確率σはたぶん小さい。
• したがって、チャイティンが停止する確率は 1 - βσ である。
• βがべらぼうに小さいので、1 - βσ はほぼ 1 である。
• 証明終わり

*1:あ、(omega n) の最小上界であって、Ωの最小上界ではないのかな。