チャイティンの定数

チャイティンの定数は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率とも。

停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。

個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。

1. 背景
-----

停止確率の定義は「接頭属性のある完備計算可能関数」の存在に依存している。そのような関数は直観的には、どの妥当なプログラムも他の妥当なプログラムの適当な拡張として得られないという属性を持つプログラミング言語で表される。

2つの引数をとる関数 //F// があり、それら引数は有限なバイナリ列であり、出力として1つのバイナリ列を返すとする。この関数を計算できるチューリングマシンがあるとき、//F// は計算可能関数と呼ばれる。

次のような属性を持つとき、この関数 //F// は計算完備であると言われる。すなわち、1つの変数 //x// の全ての計算可能関数 //f// について、あらゆる //x// について //F// = //f// となるような定数 //p// が存在する場合である。これは、//F// が1変数のあらゆる計算可能関数をシミュレートするのに使えることを意味する。大まかに言えば、//p// は計算可能関数 //f// のプログラムを表し、//F// はそのプログラムを入力としてそれを実行するエミュレータを表す。任意の定数 //p// について //f// = //F// を計算できるため、計算完備性とはあらゆる1変数の計算可能関数をこの形式で表せることを示している。

//F// の定義域は、//x// の少なくとも1つの値について //F// の値が定義されている全てのプログラム //p// の集合である。言い換えれば、その定義域は空関数以外の関数を符号化した全てのプログラムの集合である。

関数 //F// が接頭属性を持つとは、定義域に //p// と //p// の適切な拡張である //p′// が存在することはないことを意味する。言い換えれば、//F// の定義域は有限バイナリ文字列の集合上の接頭符号である。任意の完備計算可能関数の定義域は帰納的可算集合だが、帰納的集合ではない。その定義域は停止性問題とチューリング同値  である。

2. 停止確率の定義
----------

接頭属性つき完備計算可能関数 //F// の定義域を //P//F とする。すると、定数 ΩF は次のように定義される。 ここで、 は文字列 //p// の長さである。これは、//F// の定義域にある全ての //p// について一つずつ被加数が存在する級数である。定義域は接頭属性を持つ必要があるため、クラフトの不等式を考慮すると、この総和は0から1の間の実数に収束することが保証される。文脈上 //F// が明らかであれば ΩF を単に Ω と書いても良いが、接頭属性つき完備計算可能関数が異なれば、そこから導かれるΩの値は異なる。

3. 数論の未解決問題への応用
---------------

チャイティンの定数は、原理的には、ゴールドバッハ予想やリーマン予想といった数論の未解決問題を解くのに用いることが出来る。ゴールドバッハ予想とは、2より大きい全ての偶数は2つの素数の和で表せる、というものである。ある偶数が与えられたとき、それを2つの素数の和に分解するプログラムを考える。ゴールドバッハ予想が正しければ、このプログラムは偶数を次々に2つの素数に分解していくだろう。素数に分解できない偶数という反例が見つかった場合、プログラムは停止し、ゴールドバッハ予想は間違いだったことが示される。このプログラムの長さを //N// ビットとする。計算資源と時間に制限がない場合、チャイティンの定数を使ってゴールドバッハ予想を次のように証明できる。同時並行的に、長さが //N// + 1 ビット以下であるような全てのプログラムを実行する。//N//ビットであるゴールドバッハプログラムが停止すれば、予想は偽であったと証明される。もしこの逆に、他のプログラムがどんどん停止してあと一つでも停止すればチャイティンの定数を超えてしまう状況となり、その時点でまだゴールドバッハプログラムが停止していないなら、最早ゴールドバッハプログラムは停止し得ないので、ゴールドバッハ予想が正しいことが証明される。この方法を用いる上では、チャイティンの定数の先頭から //N// + 1 ビットまでの値さえ分かればよい。

同様に、リーマン予想などの数学上の未解決問題の多くも、チャイティンの定数を使って証明できる。

上の説明は再帰的公理化可能理論の可証性述語がチャイティン定数から相対的に計算可能であるということを示しているに過ぎない。上記の方法で未解決問題の可証性を判定するために必要なビット長は長大であり、チャイティン定数の正確な値を必要なだけ求めることは困難である。仮に必要なだけのビットが求められたとしても、上のアルゴリズムの計算量は膨大である。したがって上記の方法で未解決問題の可証性を判定することが実際的な意味で可能であるというわけではない。

4. 確率としての解釈
-----------

0と1のあらゆる無限の並びの集合をカントール空間と呼ぶ。停止確率は、カントール空間上の通常の確率測度におけるカントール空間のある部分集合の測度と解釈できる。

カントール空間上の確率測度は、任意のバイナリ列 //x// について //x// で始まるバイナリ列の集合の測度が 2-|//x//| となるよう定義される。それぞれの自然数 //n// について、カントール空間内のバイナリ列の集合 //f// が //f// = 1 であるとき、その測度は 1/2 であり、//n// 番目の要素が 0 であるバイナリ列の集合の測度も 1/2 である。

//F// を接頭属性のある完備計算可能関数であるとする。//F// の定義域 //P// は次のような無限のバイナリ文字列の集合である。 個々の文字列 //p////i// は、カントール空間の部分集合 //S////i// に対応する。集合 //S////i// は //p////i// で始まるカントール空間内の全てのバイナリ列を含む。//P// は接頭属性を持つため、これらの集合は重ならない。総和 は次の集合の測度を表す。

かくして、Ω//F// は、無作為に選択された 0 と 1 から成る無限列が、//F// の定義域にあるようなビット列から始まる確率を表している。Ω//F// が停止確率と呼ばれるのはこのことが理由である。

5. 属性
-----

チャイティンの定数 Ω は以下のような属性を有する。

アルゴリズム的無作為性を有する。すなわち、任意の特定のプログラミング言語において定数 //C// が存在し、その言語で書かれたチャイティンの定数の先頭 //n// ビットを出力して停止するプログラムは、 ビットより短くなることはない。
正規数である。すなわち、歪みの無い硬貨を投げて決めたように各数字が等しい確率で出現する。
計算可能数ではない。すなわち、バイナリ列として展開した値を計算できる関数は存在しない。
//q// ≤ Ω となる有理数 //q// の集合は帰納的可算集合である。このような属性を持つ実数を再帰理論では 左-c.e.実数 と呼ぶ。
停止問題とチューリング同値であり、したがって算術的階層の に属する。停止問題とチューリング同値なあらゆる集合が停止確率というわけではない。より強い同値関係