停止確率の不完全性定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/29 09:02 UTC 版)
「チャイティンの定数」の記事における「停止確率の不完全性定理」の解説
詳細は「コルモゴロフ複雑性#チャイティンの不完全性定理」を参照 自然数を扱う無矛盾で有効に表現された公理系（例えばペアノ算術など）それぞれにおいて、Ωの値を求める際、Ω の先頭 N ビットを過ぎてしまうと、以降はそれらの体系内でΩの桁が 0 なのか 1 なのか証明できないような定数 N が存在する。定数 N の値は、その形式体系がどのように有効に表現されているかに依存し、従ってその公理体系の複雑さを直接反映しない。この不完全性は、算術のどのような無矛盾な形式的理論も完全でないことを示すゲーデルの不完全性定理に類似している。
※この「停止確率の不完全性定理」の解説は、「チャイティンの定数」の解説の一部です。
「停止確率の不完全性定理」を含む「チャイティンの定数」の記事については、「チャイティンの定数」の概要を参照ください。
ウィキペディア小見出し辞書の「停止確率の不完全性定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 停止確率の不完全性定理のページへのリンク
