Inter-universal geometry と ABC予想 (応援スレ) 71 (587ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) ﾚｽ栞 あぼーん
295(2): 05/05(日)00:01 ID:HvNo6+XN(1/8) AAS
>>294
>停止問題wwwwwww
>必ず判定検査が停止するのがrecursive setやアホタレwwwwww
>流石にこのレベルの話はネットにいくらでも解説記事転がっとるわ
おもろいオッサンやね
１）recursive set＝Computable set かな
”if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not.”
だね？
２)ところで、問題は「ある論文の証明を、定理証明システムに乗せて、コンピュータを走らせたとき、必ず停止するか？」ってことだよね
最初から”recursive set”を仮定するなら良いが、その仮定がないときは「必ず停止する」は言えないよｗ
省20
299(1): 05/05(日)08:30 ID:HvNo6+XN(2/8) AAS
>>296-297
>recursiveだから正しければ“正しい”と出力して停止し、間違いなら“間違い”と出力して停止するわ
おもろいオッサンやね
１）”recursive”を仮定すれば、その通りだが
いま問題にしていることは、そうではない
『現在および将来における数学論文の証明が、コンピュータの証明支援システムにかけたときに
必ず停止するか？』ってことよ
”recursive”（つまりComputable >>295）の仮定は、保証されていない！
２）別の問題に、有限時間で停止するとしても、”P≠NP予想”のような『計算複雑性理論（計算量理論）』問題もある
つまり、コンピュータの証明支援システムがある有限時間T1で停止しないとき、さらに計算を続けるべきかどうか？
省10
300: 05/05(日)08:37 ID:HvNo6+XN(3/8) AAS
>>298
面白いやつだな
この数学証明のコンピュータ支援システムの停止問題論争は
見る人が見れば、どっちの勝ちかは自明だよ
303(1): 05/05(日)11:32 ID:HvNo6+XN(4/8) AAS
>>301-302
>recursiveになるように設計されとる言うてるやろアホ〜wwwww
・recursive, Computable set >>295 の問題は
原理的な話だから、設計云々関係ないわなｗ
（設計で解決できる問題ではないよｗｗ）
>そして計算量wwwwwwwww
>心配せんでも計算量クラスもPじゃボケ〜
１）まず、証明がない
２）次に、あんたの”クラスP”理論を、IUTに適用してみろ！ 具体にどんな多項式になるの？ｗｗ
３）そもそも、”recursive, Computable set”が保証されていない！！ｗｗｗ
304(1): 05/05(日)12:02 ID:HvNo6+XN(5/8) AAS
これ、参考になるだろう
外部ﾘﾝｸ:zenn.dev
zenn /mineel
停止性問題と不完全性定理
2023/08/12
はじめに
巷では「停止性問題は不完全性定理と深いつながりがある」みたいな主張をよく耳にしますが、その具体的な繋がりまで説明されていることは多くありません。
そこで、この記事では停止性問題が具体的にどう不完全性定理に繋がるのか解説しようと思います。
結論を言ってしまうと、「決定不能なRE集合さえあればそこから直ちに第一不完全性定理が導ける」というだけの話であり、ちょうど手頃な具体例に停止性問題があっただけで別に停止性問題である必然性はありません。
なので、私は停止性問題と不完全性定理には本質的なつながりはないと考えております。
省11
326: 05/05(日)20:26 ID:HvNo6+XN(6/8) AAS
>>324-325
>証明の構文規則にあてはまっているかどうかチェックするだけなので決定可能
>つまりギャップがある時点で証明ではない
１）上記の数学的な証明ないし
それが既に数学の理論になっていることの 文献の裏付けやいかに！？（自分で探してねｗ）ｗ
（まず、証明の構文規則なるものの列挙とその定義がいるよねｗｗ）
２）『証明の構文規則にあてはまっているかどうか』でいえば
ZFCから作られる集合は、すべてZFCの構文規則に当てはまっているでしょ？
じゃあ、なんで不完全性定理がある？
（そもそも、IUTはZFCの外＝ZFCGで、到達不能基数の存在を仮定するという。どうすんの？ｗ）
省12
331(1): 05/05(日)23:29 ID:HvNo6+XN(7/8) AAS
ご参考
”結論:多くのプログラム言語に対して、その言語で書かれたプログラムの停止性は、決定可能ではない”
//www.cs.tsukuba.ac.jp/~kam/lecture/plm2017/
2017年度の『プログラム言語論』亀山幸義筑波大学情報科学
//www.cs.tsukuba.ac.jp/~kam/lecture/plm2017/termination.pdf
講義資料
プログラム言語論亀山幸義筑波大学情報科学類No.4(停止性)
停止性問題
以下の性質を持つプログラムHは存在するか？
・Hは2引数関数である。
省24
332(1): 05/05(日)23:45 ID:HvNo6+XN(8/8) AAS
>>328
>//ja.m.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%A8%80%E8%AA%9E%E3%81%AE%E9%9A%8E%E5%B1%A4
(引用開始)
形式言語の階層
個々の言語クラスの解説
チョムスキー階層の言語クラスごとに解説する。
タイプ-0内
帰納的可算言語は、部分決定性言語またはチューリング受理性言語とも呼ばれ、対応するオートマトンであるチューリングマシンが受理しない文字列の入力で停止する事が保証されていない言語のクラスである。これを決定性のある、つまりチューリングマシンが常に停止する言語に限定したクラスが帰納言語で、決定性言語またはチューリング決定性言語とも呼ばれる。
これらの計算複雑性はそれぞれ複雑性クラスRとREに対応する。
(引用終り)
省11
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.022s