23/01/04 21:56:03.91 e78Zodr8.net
>>417
ありがとう
下記な
”チャイティンの定数：個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない”（下記）
これは、時枝 ｽﾚﾘﾝｸ(math板)
と、バッティングしているかもｗ
(参考)
URLﾘﾝｸ(ja.wikipedia.org)
チャイティンの定数
チャイティンの定数（チャイティンのていすう、英: Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、英: Halting probability）とも。
停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。
個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。
数論の未解決問題への応用
チャイティンの定数は、原理的には、ゴールドバッハ予想やリーマン予想といった数論の未解決問題を解くのに用いることが出来る[1]。ゴールドバッハ予想とは、2より大きい全ての偶数は2つの素数の和で表せる、というものである。ある偶数が与えられたとき、それを2つの素数の和に分解するプログラムを考える。ゴールドバッハ予想が正しければ、このプログラムは偶数を次々に2つの素数に分解していくだろう。素数に分解できない偶数という反例が見つかった場合、プログラムは停止し、ゴールドバッハ予想は間違いだったことが示される。このプログラムの長さを N ビットとする。計算資源と時間に制限がない場合、チャイティンの定数を使ってゴールドバッハ予想を次のように証明できる。同時並行的に、長さが N + 1 ビット以下であるような全てのプログラムを実行する。Nビットであるゴールドバッハプログラムが停止すれば、予想は偽であったと証明される。
つづく