チャイティンの定数

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

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

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

背景

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

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

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

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

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

停止確率の定義

接頭属性つき完備計算可能関数 F の定義域を P_F とする。すると、定数 Ω_F は次のように定義される。

$\Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}$

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

数論の未解決問題への応用

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

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

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

確率としての解釈

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

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

F を接頭属性のある完備計算可能関数であるとする。F の定義域 P は次のような無限のバイナリ文字列の集合である。

$P=\{p_{1},p_{2},\ldots \}$

個々の文字列 p_i は、カントール空間の部分集合 S_i に対応する。集合 S_i は p_i で始まるカントール空間内の全てのバイナリ列を含む。P は接頭属性を持つため、これらの集合は重ならない。総和

$\sum _{p\in P}2^{-|p|}$

は次の集合の測度を表す。

$\bigcup _{i\in \mathbb {N} }S_{i}$

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

属性

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

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

停止問題とチューリング同値なあらゆる集合が停止確率というわけではない。より強い同値関係（Solovay equivalence) を用いて、左-c.e.実数の中で停止確率を特徴付けることができる。

停止確率の計算不可能性

ある実数が計算可能であるとは、n を入力として与えられたとき、その実数の先頭から n 桁を出力するアルゴリズムが存在する場合である。これは、実数の数字を列挙するプログラムの存在と等価である。

停止確率は計算可能ではない。この事実の証明は、Ω の先頭 n 桁を与えるアルゴリズムがあるとすれば、そのアルゴリズムを用いれば長さ n までのプログラムの停止問題が解けてしまうことに拠る。停止問題は決定不能であるため、矛盾が生じ、Ω が計算できないことが示される。

このアルゴリズムは次のように進行する。Ω の先頭 n 桁と k ≤ n が与えられているとして、アルゴリズムは F の定義域を数え上げていき、数え上げた要素群が表す確率が Ω の 2^-(k+1) 以内である限り続ける。この時点を過ぎると、最早長さ k であるような如何なるプログラムも定義域に存在し得ない。何故なら、もしそのようなプログラムがあれば、それぞれが測度に 2^-k を追加することになってしまい、これは不可能だからである。従って、定義域内の長さ k の文字列の集合は、まさに既に列挙した文字列の集合である。

停止確率の不完全性定理

→詳細は「コルモゴロフ複雑性 § チャイティンの不完全性定理」を参照

自然数を扱う無矛盾で有効に表現された公理系（例えばペアノ算術など）それぞれにおいて、Ωの値を求める際、Ω の先頭 N ビットを過ぎてしまうと、以降はそれらの体系内でΩの桁が 0 なのか 1 なのか証明できないような定数 N が存在する。定数 N の値は、その形式体系がどのように有効に表現されているかに依存し、従ってその公理体系の複雑さを直接反映しない。この不完全性は、算術のどのような無矛盾な形式的理論も完全でないことを示すゲーデルの不完全性定理に類似している。

スーパーオメガ

上述したように、チャイティンの定数 Ω の先頭 n ビットは、n-Ｏ(1)ビット未満の停止するアルゴリズムで計算できないという意味において、ランダムまたは圧縮不可能である。しかし、あらゆるプログラムを体系的に列挙して実行する、短くて停止しないアルゴリズムがあるとする。このとき、列挙されたプログラムが停止する場合は、その確率を出力（初期値は0）に加算する。ある有限時間が経過すると、出力の先頭 n ビットはそれ以上変化しなくなる（この経過時間自体が停止するプログラムで計算できないことは、ここでは重要ではない）。従って、その出力が有限時間内に Ω の先頭 n ビット（n は任意）に収束するような停止しない短いアルゴリズムが存在する。言い換えれば、Ω の枚挙可能な先頭 n ビットは、非常に短いアルゴリズムで極限計算可能という意味で、圧縮可能である。つまり数え上げアルゴリズムの集合という観点からはランダムではない。Jürgen Schmidhuber(en) (2000) は、極限計算可能な「スーパーオメガ」を構築したが、これはオリジナルの極限計算可能なΩ（オメガ）よりも或る意味で更にランダムである。スーパーオメガは、停止しない如何なる数え上げアルゴリズムを用いてもあまり圧縮できない。

脚注

^ Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd Edition, Wiley-Interscience, 2006.

参考文献

Cristian S. Calude (2002). Information and Randomness: An Algorithmic Perspective, second edition. Springer. ISBN 3-5404-3466-6
Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. Computing a Glimpse of Randomness.
R. Downey, and D. Hirschfeldt (200?), Algorithmic Randomness and Complexity, monograph in preparation, Springer-Verlag. 準備稿はこちらにある。
Ming Li and Paul Vitányi (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. 概要部分の全文はこちら
Jürgen Schmidhuber (2000). Algorithmic Theories of Everything (arXiv: quant-ph/ 0011122). Journal reference: J. Schmidhuber (2002). Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612.

外部リンク

Omega and why math has no TOEs グレゴリー・チャイティンの論文に基づいた記事。2004年8月。Mathematics Today（アラン・チューリング没後50周年記念）
The Limits of Reason, Gregory Chaitin, オリジナルは Scientific American, March 2006.
Limit-computable Super Omega more random than Omega and generalizations of algorithmic information, by Jürgen Schmidhuber

[1] Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd Edition, Wiley-Interscience, 2006.

[1]

背景