チャイティン定数

コンピュータサイエンスのアルゴリズム情報理論の分野において、チャイティン定数（チャイティンオメガ数）^[1]または停止確率は、非公式に言えば、ランダムに構築されたプログラムが停止する確率を表す実数です。これらの数値は、グレゴリー・チャイティンによる構成から形成されます。

停止確率は、プログラムをエンコードする各方法 (普遍的、下記参照) ごとに 1 つずつ、無限に存在しますが、文字 Ω を使用して、停止確率が 1 つしかないかのように参照するのが一般的です。Ω は使用されるプログラム エンコードに依存するため、特定のエンコードを参照しない場合は、チャイティンの構成と呼ばれることがあります。

各停止確率は計算不可能な通常の超越実数であり、つまりその桁を計算するアルゴリズムは存在しません。各停止確率はMartin-Löf 乱数であり、つまりその桁を確実に推測できるアルゴリズムすら存在しません。

停止確率の定義は、プレフィックスフリーの普遍的な計算可能関数の存在に依存します。 直感的に言えば、このような関数は、別の有効なプログラムの適切な拡張として有効なプログラムを取得できないという特性を持つプログラミング言語を表します。

ただし、コンピュータ プログラミング言語は一般に一連のコマンドから構成されるため、プレフィックスのない普遍的な計算可能な関数であるプログラミング言語はありません。

F が、有限のバイナリ文字列を 1 つの引数として受け取り、出力として 1 つのバイナリ文字列を返す可能性のある部分関数であるとします。関数Fは、それを計算するチューリング マシンが存在する場合、計算可能と呼ばれます。つまり、任意の有限のバイナリ文字列xとy に対して、チューリング マシンが入力x を与えられたときにテープ上にyがある状態で停止する場合に限り、 F(x) = yとなります。

関数F は、次の特性が成り立つ場合、ユニバーサル関数と呼ばれます。単一変数のすべての計算可能関数fに対して、すべてのxに対してF ( w x ) = f ( x )となる文字列wが存在します。ここで、w x は2 つの文字列wとxの連結を表します。つまり、 F は、単一変数の任意の計算可能関数をシミュレートするために使用できます。非公式には、w は計算可能関数fの「スクリプト」を表し、F は、スクリプトを入力のプレフィックスとして解析し、入力の残りの部分で実行する「インタープリター」を表します。   

Fの定義域は、それが定義されるすべての入力pの集合です。普遍的なFの場合、そのようなp は一般に、プログラム部分とデータ部分の連結として、また関数Fの単一のプログラムとして見ることができます。

関数F は、その定義域に2 つの要素p、p′が存在せず、 p′ がpの適切な拡張ではない場合、プレフィックスフリーと呼ばれます。これは、次のように言い換えることができます。Fの定義域は、有限バイナリ文字列の集合上のプレフィックスフリーコード（瞬時コード）です。プレフィックスフリーを強制する簡単な方法は、入力手段が 1 ビットずつ読み取ることができるバイナリストリームであるマシンを使用することです。ストリームの終了マーカーはありません。入力の終了は、汎用マシンがそれ以上のビットの読み取りを停止することを決定した時点によって決定され、残りのビットは受け入れられた文字列の一部とは見なされません。ここで、前の段落で述べたプログラムの 2 つの概念の違いが明らかになります。1 つは何らかの文法で簡単に認識できますが、もう 1 つは認識するために任意の計算が必要です。

あらゆる普遍計算可能関数の定義域は計算可能列挙集合であるが、計算可能集合には決してならない。その定義域は常に停止問題とチューリング同値である。

P _{F を}プレフィックスフリーの普遍計算可能関数Fの定義域とする。定数 Ω _Fは次のように定義される。

${\displaystyle \Omega_{F}=\sum_{p\inP_{F}}2^{-|p|}}$、

ここで、 は文字列pの長さを表します。これは、Fの定義域にあるすべてのpに対して 1 つの加数を持つ無限和です。定義域が接頭辞なしであるという要件とクラフトの不等式により、この和は0 から 1 の間の実数に収束します。 F が文脈から明らかな場合、 Ω _{F は}単に Ω と表記されますが、異なる接頭辞なしのユニバーサル計算可能関数は異なる Ω の値をもたらします。 ${\displaystyle \left|p\right|}$

Ω の最初のNビットがわかれば、 Nまでのサイズのすべてのプログラムについて停止問題を計算できます。停止問題を解決するプログラムp をNビットの長さとします。dovetailing 方式で、すべての長さのすべてのプログラムが実行され、十分な数のプログラムが停止して、最初のNビットに一致する確率が共同で寄与するまで続きます。プログラムpがまだ停止していない場合は、停止確率への寄与が最初のNビットに影響するため、停止することはありません。したがって、停止問題はpについて解決されます。

ゴールドバッハの予想など、数論における多くの未解決の問題は、特別なプログラム（基本的に反例を検索し、見つかった場合は停止する）の停止問題を解くことと同等であるため、チャイティン定数の十分なビットを知っていることは、これらの問題の答えも知っていることを意味します。しかし、停止問題は一般には解決できず、したがってチャイティン定数の最初の数ビット以外を計算することは非常に簡潔な言語では不可能であるため、これは困難な問題を不可能な問題に減らすだけです。これは、停止問題の神託マシンを構築しようとするのと同じです。

カントール空間は、0 と 1 の無限シーケンスすべての集合です。停止確率は、カントール空間上の通常の確率測定によるカントール空間の特定のサブセットの測定として解釈できます。この解釈から、停止確率の名前が付けられています。

カントール空間上の確率測度は、フェアコイン測度とも呼ばれ、任意のバイナリ文字列xに対して、 xで始まるシーケンスの集合が測度 2 ^{−| x |}を持つように定義されます。これは、各自然数nに対して、 f ( n ) = 1となるカントール空間内のシーケンスfの集合が測度 1/2 を持ち、 n番目 の要素が 0 であるシーケンスの集合も測度 1/2 を持つことを意味します。

Fをプレフィックスフリーの普遍計算可能関数とする。FのドメインPはバイナリ文字列の無限集合から構成される 。

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

これらの文字列p _{i は}それぞれカントール空間の部分集合S _iを決定する。集合S _iにはカントール空間でp _iで始まるすべてのシーケンスが含まれる。Pは接頭辞のない集合である ため、これらの集合は互いに素である。

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

集合の大きさを表す

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

このように、 Ω _{F は、}ランダムに選択された 0 と 1 の無限シーケンスが、 Fのドメインにあるビット文字列 (ある有限の長さ) で始まる確率を表します。このため、 Ω _{F は}停止確率と呼ばれます。

各チャイティン定数Ωには次の特性があります。

• これはアルゴリズム的にランダムです（Martin-Löfランダムまたは1ランダムとも呼ばれます）。^[2]これは、Ωの最初のnビットを出力する最短のプログラムのサイズが少なくともn − O(1)でなければならないことを意味します。これは、ゴールドバッハの例のように、それらのnビットによって、長さが最大でnのすべてのプログラムの中でどのプログラムが停止するかを正確に見つけることができるためです。
• 結果として、これは正規数であり、その数字は公平なコインを投げて生成されたかのように均等に分布していることを意味します。
• これは計算可能な数ではありません。以下で説明するように、その 2 進展開を列挙する計算可能な関数は存在しません。
• q < Ωとなるような有理数 qの集合は計算可能に列挙可能である。^[3]このような性質を持つ実数は再帰理論において左辺実数と呼ばれる。
• q > Ωとなるような有理数qの集合は、計算可能列挙可能ではありません。(理由: この特性を持つすべての左辺 ce 実数は計算可能ですが、Ω は計算できません。)
• Ω は算術数です。
• これは停止問題とチューリング同等であり、したがって算術階層のレベルにあります。${\displaystyle \Delta _{2}^{0}}$

停止問題とチューリング同値であるすべての集合が停止確率であるわけではない。より細かい同値関係であるソロベイ同値関係は、左辺 ce の実数間の停止確率を特徴付けるために使用できる。^[4] [0,1] の実数がチャイティン定数（つまり、プレフィックスのないユニバーサル計算可能関数の停止確率）であるのは、それが左辺 ce かつアルゴリズム的にランダムである場合のみであることを示すことができる。 [ ^{4] Ω は、}定義可能なアルゴリズム的にランダムな数が少ないうちの 1 つであり、最もよく知られているアルゴリズム的にランダムな数であるが、すべてのアルゴリズム的にランダムな数の典型的な数ではない。^[5]

実数は、nが与えられたときにその数の最初のn桁を返すアルゴリズムが存在する場合、計算可能と呼ばれます。これは、実数の桁を列挙するプログラムが存在することと同等です。

停止確率は計算できません。この事実の証明は、Ω の最初のn桁が与えられた場合に、長さがnまでのプログラムに対するチューリングの停止問題を解くアルゴリズムに依存します。停止問題は決定不可能であるため、Ω は計算できません。

アルゴリズムは次のように進行します。 Ω の最初のn桁とk ≤ nが与えられると、アルゴリズムはFのドメインを列挙し、十分な数のドメイン要素が見つかり、それらが表す確率が Ω の 2 ^{−( k +1)以内になるまで続けます。この時点以降、長さ}kのプログラムがドメインに追加されることはありません。これは、これらを追加すると測定値に 2 ^{− k が}追加されるため、不可能だからです。したがって、ドメイン内の長さkの文字列の集合は、すでに列挙されている文字列の集合とまったく同じです。

実数は、その実数を表す2進数列がアルゴリズム的にランダムな列である場合にランダムである。Calude、Hertling、Khoussainov、Wangは^[6]、再帰的に列挙可能な実数がアルゴリズム的にランダムな列となるのは、それがChaitinのΩ数である場合のみであることを示した。

ペアノ算術のような、自然数に対する特定の一貫した効果的に表現された公理系ごとに、定数Nが存在し、そのシステム内でN番目以降の Ω のどのビットも1 か 0 であると証明することはできません。定数N は形式システムが効果的に表現される方法に依存するため、公理系の複雑さを直接反映するものではありません。この不完全性の結果は、算術に対する一貫した形式理論は完全ではあり得ないことを示す点で、 ゲーデルの不完全性定理に似ています。

上で述べたように、グレゴリー・チャイティンの定数 Ωの最初の n ビットは、nO(1) ビット未満の停止アルゴリズムでは計算できないという意味でランダムまたは非圧縮です。しかし、すべての可能なプログラムを体系的にリストして実行する、短いが決して停止しないアルゴリズムを考えてみましょう。そのうちの 1 つが停止するたびに、その確率が出力に追加されます (ゼロで初期化されます)。有限時間が経過すると、出力の最初の n ビットはそれ以上変化しません (この時間自体が停止プログラムによって計算可能でないことは問題ではありません)。したがって、有限時間が経過すると出力が Ω の最初の n ビットに収束する短い非停止アルゴリズムが存在します。言い換えると、 Ω の列挙可能な最初の n ビットは、非常に短いアルゴリズムで極限計算可能であるという意味で高度に圧縮可能であり、列挙アルゴリズムの集合に関してランダムではありません。 Jürgen Schmidhuber (2000) は、限界計算可能な「Super Ω」を構築しました。これは、いかなる列挙型非停止アルゴリズムでも Super Ω を大幅に圧縮できないため、ある意味では元の限界計算可能な Ω よりもはるかにランダムです。

別の「スーパーΩ」として、プレフィックスのないユニバーサルチューリングマシン（UTM）の普遍性確率、つまり、UTMのすべての入力（バイナリ文字列）の前にランダムなバイナリ文字列が付けられた場合でもUTMが普遍性を維持する確率は、停止問題の3回目の反復（つまり、チューリングジャンプ表記法を使用）を予言するマシンの非停止確率として考えることができます。^[7] ${\displaystyle O^{(3)}}$

• ゲーデルの不完全性定理
• コルモゴロフ複雑性

• Calude, Cristian S. (2002)。情報とランダム性：アルゴリズムの観点（第2版）。Springer。ISBN 3-540-43466-6。
• Downey, R.; Hirschfeldt, D. (2010).アルゴリズムのランダム性と複雑性. Springer-Verlag.
• Li, Ming; Vitányi, Paul (1997).コルモゴロフ複雑性とその応用への入門. Springer.序章の全文。
• Schmidhuber, Jürgen (2002). 「一般化されたコルモゴロフ複雑度の階層と極限で計算可能な非数え切れない普遍的測度」International Journal of Foundations of Computer Science . 13 (4): 587–612. doi :10.1142/S0129054102001291.プレプリント: 万物のアルゴリズム理論 (arXiv: quant-ph/ 0011122)

• チャイティンのオメガの研究における最近の進歩について議論するチャイティンのオメガ調査記事の側面。
• オメガと数学に TOE がない理由に関する記事は、アラン・チューリングの死後 50 周年を記念して 2004 年 8 月の Mathematics Today に掲載されたGregory Chaitin氏の記事に基づいています。
• グレゴリー・チャイティン著『理性の限界』は、もともと Scientific American 誌 2006 年 3 月号に掲載されました。
• オメガよりもランダムな極限計算可能なスーパーオメガとアルゴリズム情報の一般化、Jürgen Schmidhuber著