チャイティンの定数のソースを表示

'''チャイティンの定数'''（チャイティンのていすう、{{lang-en-short|Chaitin's constant}}）は、[[計算機科学]]の一分野である[[アルゴリズム情報理論]]の概念で、非形式的に言えば無作為に選択されたプログラムが停止する[[確率]]を表した[[実数]]である。[[グレゴリー・チャイティン]]の研究から生まれた。'''停止確率'''（ていしかくりつ、{{lang-en-short|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&prime;'' が存在することはないことを意味する。言い換えれば、''F'' の定義域は有限バイナリ文字列の集合上の[[接頭符号]]である。任意の完備計算可能関数の定義域は[[帰納的可算集合]]だが、[[帰納的集合]]ではない。その定義域は[[停止性問題]]とチューリング同値 (Turing equivalent) である。

== 停止確率の定義 ==
接頭属性つき完備計算可能関数 ''F'' の定義域を ''P''<sub>F</sub> とする。すると、定数 Ω<sub>F</sub> は次のように定義される。
{{Indent|<math>\Omega_F = \sum_{p \in P_F} 2^{-|p|}</math>}}
ここで、<math>\left|p\right|</math> は文字列 ''p'' の長さである。これは、''F'' の定義域にある全ての ''p'' について一つずつ被加数が存在する[[級数]]である。定義域は接頭属性を持つ必要があるため、[[クラフトの不等式]]を考慮すると、この総和は0から1の間の[[実数]]に収束することが保証される。文脈上 ''F'' が明らかであれば Ω<sub>F</sub> を単に Ω と書いても良いが、接頭属性つき完備計算可能関数が異なれば、そこから導かれるΩの値は異なる。

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

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

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

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

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

''F'' を接頭属性のある完備計算可能関数であるとする。''F'' の定義域 ''P'' は次のような無限のバイナリ文字列の集合である。
{{Indent|<math>P = \{p_1,p_2,\ldots\}</math>}}
個々の文字列 ''p''<sub>''i''</sub> は、カントール空間の部分集合 ''S''<sub>''i''</sub> に対応する。集合 ''S''<sub>''i''</sub> は ''p''<sub>''i''</sub> で始まるカントール空間内の全てのバイナリ列を含む。''P'' は接頭属性を持つため、これらの集合は重ならない。総和
{{Indent|<math>\sum_{p \in P} 2^{-|p|}</math>}}
は次の集合の測度を表す。
{{Indent|<math>\bigcup_{i \in \mathbb{N}} S_i</math>}}

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

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

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

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

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

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

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

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

== 関連項目 ==
* [[コルモゴロフ複雑性]]
* [[ゲーデルの不完全性定理]]

== 脚注 ==
{{Reflist}}

== 参考文献 ==
*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. ''[http://www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf Computing a Glimpse of Randomness].''
*R. Downey, and D. Hirschfeldt (200?), ''Algorithmic Randomness and Complexity'', monograph in preparation, Springer-Verlag. 準備稿は[http://www.mcs.vuw.ac.nz/~downey こちら]にある。
* Ming Li and Paul Vitányi (1997).  ''An Introduction to Kolmogorov Complexity and Its Applications''. Springer. [http://citeseer.ist.psu.edu/li97introduction.html 概要部分の全文はこちら]
* 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.

==外部リンク==
* [http://www.plus.maths.org.uk/issue37/features/omega/index.html Omega and why math has no TOEs] [[グレゴリー・チャイティン]]の論文に基づいた記事。2004年8月。Mathematics Today（アラン・チューリング没後50周年記念）
* [http://www.cs.auckland.ac.nz/CDMTCS/chaitin/sciamer3.html ''The Limits of Reason''], Gregory Chaitin, オリジナルは Scientific American, March 2006.
* [http://www.idsia.ch/~juergen/kolmogorov.html Limit-computable Super Omega more random than Omega] and generalizations of algorithmic information, by Jürgen Schmidhuber

{{DEFAULTSORT:ちやいていんのていすう}}

[[Category:アルゴリズム的情報理論]]
[[Category:計算理論]]
[[Category:定数]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]