[過去ﾛｸﾞ] 純粋・応用数学・数学隣接分野（含むガロア理論）12 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
424(1): 現代数学の系譜 雑談 ◆yH25M02vWFhP 2023/01/04(水)21:56 ID:e78Zodr8(5/5) AAS
>>423
つづき
停止確率は計算可能ではない。この事実の証明は、Ω の先頭 n 桁を与えるアルゴリズムがあるとすれば、そのアルゴリズムを用いれば長さ n までのプログラムの停止問題が解けてしまうことに拠る。停止問題は決定不能であるため、矛盾が生じ、Ω が計算できないことが示される。
このアルゴリズムは次のように進行する。Ω の先頭 n 桁と k =< n が与えられているとして、アルゴリズムは F の定義域を数え上げていき、数え上げた要素群が表す確率が Ω の 2-(k+1) 以内である限り続ける。この時点を過ぎると、最早長さ k であるような如何なるプログラムも定義域に存在し得ない。何故なら、もしそのようなプログラムがあれば、それぞれが測度に 2-k を追加することになってしまい、これは不可能だからである。従って、定義域内の長さ k の文字列の集合は、まさに既に列挙した文字列の集合である。
停止確率の不完全性定理
詳細は「コルモゴロフ複雑性#チャイティンの不完全性定理」を参照
自然数を扱う無矛盾で有効に表現された公理系（例えばペアノ算術など）それぞれにおいて、Ωの値を求める際、Ω の先頭 N ビットを過ぎてしまうと、以降はそれらの体系内でΩの桁が 0 なのか 1 なのか証明できないような定数 N が存在する。定数 N の値は、その形式体系がどのように有効に表現されているかに依存し、従ってその公理体系の複雑さを直接反映しない。この不完全性は、算術のどのような無矛盾な形式的理論も完全でないことを示すゲーデルの不完全性定理に類似している
省2
425(1): 2023/01/05(木)06:07 ID:ui+6CINH(1/3) AAS
>>422-424
また、１が生半可に知って、🐎🦌なこといってんな
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
チャイティンの定数
個々の停止確率は正規かつ超越的な実数であり、計算不可能である。
つまりその各桁を列挙するアルゴリズムは存在しない
これは、箱入り無数目
省11
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.040s