|
チャイティンの定数（チャイティンのていすう、）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも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) である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「チャイティンの定数」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Chaitin's constant 」があります。 スポンサード リンク
|