Inter-universal geometry と ABC予想 (応援スレ) 71 (587ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) ﾚｽ栞 あぼーん
307: 05/05(日)14:27 ID:WLbxyLlj(1/5) AAS
>>304
>結論を言ってしまうと、「決定不能なRE集合さえあればそこから直ちに第一不完全性定理が導ける」というだけの話であり、ちょうど手頃な具体例に停止性問題があっただけで別に停止性問題である必然性はありません。
304です
・RE集合を補足します（下記）
・下記では、”複雑性クラス RE（recursively enumerable）”であって、集合ではなくクラスとしていますね ；ｐ）
・あと、下記に再録したように、「定理3：（停止性問題は決定不能）」の証明に、対角線論法が出てきます
これは、第一不完全性定理と同じスジです
(参考)
//ja.wikipedia.org/wiki/RE_(%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)
RE (計算複雑性理論)
省8
308(1): 05/05(日)14:29 ID:WLbxyLlj(2/5) AAS
つづき
//ja.wikipedia.org/wiki/R_(%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)
R (計算複雑性理論)
計算複雑性理論において、複雑性クラス R とは、チューリングマシンで解ける決定問題の集合であり、全ての帰納言語の集合に相当する。R はしばしば、「効率的に計算可能な」関数のクラスと言われる（チャーチ＝チューリングのテーゼ）。
任意の決定問題の解法として、その問題のリコグナイザと補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。
したがって、このクラスは RE を使って
� RE∩coRE と定義できる。
（再録）
//zenn.dev/mineel5/articles/db3e410a05e2d8
zenn /mineel
省23
309: 05/05(日)14:37 ID:WLbxyLlj(3/5) AAS
>>306
>2011年にWill Sawinは17歳でYale を卒業。数学と経済学のdouble major。
>じゃあ、2024年現在で30歳か。
スゲー
望月さんとのRIMSでの５日間公開タイマン希望
審判員３人つけて、主審１副審２で、どっちに軍配上がるかやってほしい ；ｐ）
・・・って、Will Sawin氏は、IUT肯定派だったりしてね ＾＾）
311: 05/05(日)15:33 ID:WLbxyLlj(4/5) AAS
>>310
計算複雑性、チューリングマシン、第一不完全性定理、対角線論法ね
みんな 20世紀から知っている古い話だからね
理解とか他人の心をエスパーされても
あんた超能者なの？ってことｗｗ
自分の内心を他人に投影されても・・
ってことですよ
322(1): 05/05(日)18:09 ID:WLbxyLlj(5/5) AAS
>>316
(引用開始)
命題Pが証明可能か否か ではなく
命題Pの証明と称されるものPrfが証明になっているか否か
前者は決定不能だが
後者は決定可能
(引用終り)
さて、
”後者は決定可能”の証明は？ｗ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.485s*