確率としての解釈
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/03/29 09:02 UTC 版)
「チャイティンの定数」の記事における「確率としての解釈」の解説
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 , … } {\displaystyle P=\{p_{1},p_{2},\ldots \}} 個々の文字列 pi は、カントール空間の部分集合 Si に対応する。集合 Si は pi で始まるカントール空間内の全てのバイナリ列を含む。P は接頭属性を持つため、これらの集合は重ならない。総和 ∑ p ∈ P 2 − | p | {\displaystyle \sum _{p\in P}2^{-|p|}} は次の集合の測度を表す。 ⋃ i ∈ N S i {\displaystyle \bigcup _{i\in \mathbb {N} }S_{i}} かくして、ΩF は、無作為に選択された 0 と 1 から成る無限列が、F の定義域にあるような(有限長の)ビット列から始まる確率を表している。ΩF が停止確率と呼ばれるのはこのことが理由である。
※この「確率としての解釈」の解説は、「チャイティンの定数」の解説の一部です。
「確率としての解釈」を含む「チャイティンの定数」の記事については、「チャイティンの定数」の概要を参照ください。
- 確率としての解釈のページへのリンク