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