スーパーオメガ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/29 09:02 UTC 版)
「チャイティンの定数」の記事における「スーパーオメガ」の解説
上述したように、チャイティンの定数 Ω の先頭 n ビットは、n-Ｏ(1)ビット未満の停止するアルゴリズムで計算できないという意味において、ランダムまたは圧縮不可能である。しかし、あらゆるプログラムを体系的に列挙して実行する、短くて停止しないアルゴリズムがあるとする。このとき、列挙されたプログラムが停止する場合は、その確率を出力（初期値は0）に加算する。ある有限時間が経過すると、出力の先頭 n ビットはそれ以上変化しなくなる（この経過時間自体が停止するプログラムで計算できないことは、ここでは重要ではない）。従って、その出力が有限時間内に Ω の先頭 n ビット（n は任意）に収束するような停止しない短いアルゴリズムが存在する。言い換えれば、Ω の枚挙可能な先頭 n ビットは、非常に短いアルゴリズムで極限計算可能という意味で、圧縮可能である。つまり数え上げアルゴリズムの集合という観点からはランダムではない。Jürgen Schmidhuber(en) (2000) は、極限計算可能な「スーパーオメガ」を構築したが、これはオリジナルの極限計算可能なΩ（オメガ）よりも或る意味で更にランダムである。スーパーオメガは、停止しない如何なる数え上げアルゴリズムを用いてもあまり圧縮できない。
※この「スーパーオメガ」の解説は、「チャイティンの定数」の解説の一部です。
「スーパーオメガ」を含む「チャイティンの定数」の記事については、「チャイティンの定数」の概要を参照ください。
ウィキペディア小見出し辞書の「スーパーオメガ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- スーパーオメガのページへのリンク
