[過去ﾛｸﾞ]
ガロア第一論文と乗数イデアル他関連資料スレ5 (1002ﾚｽ)
ガロア第一論文と乗数イデアル他関連資料スレ5 http://rio2016.5ch.net/test/read.cgi/math/1687778456/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
271: １３２人目の素数さん [] 2023/07/03(月) 07:07:17.16 ID:x5daDujY >>269 ありがとうございます スレ主です これは謎のプロ数学者さんかな ＞圏論を使ったら数学の全知識が千頁の書物の記述に圧縮できるというようなことはまず期待できない 多分、ある分野やある手法に対しての加速定理（下記）を提供する能力が、圏論にはあるのではと思っています （一階述語のZFC vs 圏論（二階述語）かも） 下記 ゲーデルの加速定理：弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する ここまでは、期待できるかも。ある分野では 例えば、層の理論も、（証明論の）一種の加速定理かもと思っています https://ja.wikipedia.org/wiki/%E5%8A%A0%E9%80%9F%E5%AE%9A%E7%90%86 加速定理 計算複雑性理論における加速定理（かそくていり、英: speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、使用する資源がより少ない算法）の存在を示す定理である。 例 例として回文（palindrome）を認識する1-テープチューリング機械を考える。 略 同じ問題を O(n) で解く次のような2-テープチューリング機械が考えられる。 種々の加速定理 チューリング機械に関する線形加速定理は、ある時間［ないし空間］計算量 f (n) のチューリング機械を与えると、 同じ問題を解く時間［ないし空間］計算量 c f (n) のチューリング機械が存在することを示した定理である（ただし n は入力の大きさ、 c は正の定数）。 ブラムの加速定理は、時間計算量 \mathrm O (f (n)) の算法があれば、時間計算量 \mathrm O (\log f(n)) の算法も存在するような問題の存在を示す。この結果はブラムの加速定理の特別な場合である。この定理は時間計算量に限らずブラムの公理を満たす任意の複雑性の測り方に対して成り立つ。加速の度合いも計算可能関数の範囲で自由に指定できる。上の主張は複雑性測度として時間計算量を取り、加速関数を r(x, y)=2^y とした場合に相当する。 量子コンピュータに関する2次関数的加速定理は、決定性コンピュータが時間計算量 O(f(n)) で検索が実行できるなら、量子コンピュータなら同一の検索が時間計算量 O(\surd f(n) ) で実行できることを示した定理である つづく http://rio2016.5ch.net/test/read.cgi/math/1687778456/271
272: １３２人目の素数さん [] 2023/07/03(月) 07:09:03.47 ID:x5daDujY >>271 つづき 形式的体系に関する加速定理 理論 T とその拡大理論 S について 「T において証明可能な論理式で S においてはより簡単に証明できるものが存在する」 という形の定理は、計算複雑性に関する加速定理の類比として、同じく加速定理と呼ばれる。 その代表的なものとしてはゲーデルの加速定理がある。 これら異なるタイプの加速定理の間には或る種の対応が存在する。 例えば、ブラムの加速定理の変種であるハルトマニスの加速定理を用いてゲーデルの加速定理が証明できることが知られている。[1]また、エーレンフォイヒト・ミッシェルスキーの加速定理は、帰納的可算集合の加速可能性に関するある事実を用いて証明できる。[2] https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E3%81%AE%E5%8A%A0%E9%80%9F%E5%AE%9A%E7%90%86 ゲーデルの加速定理 ゲーデルの加速定理（ゲーデルのかそくていり、英: Godel's speedup theorem）は、クルト・ゲーデル[1]により証明された、数理論理学における定理である。この定理によれば、弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する、というような文が存在する。より正確にいえば、それはn階算術の体系で証明可能な命題であって、n+1階算術ではより短い証明を持つものが存在するというものである。 (引用終り) 以上 http://rio2016.5ch.net/test/read.cgi/math/1687778456/272
273: １３２人目の素数さん [] 2023/07/03(月) 07:28:22.54 ID:x5daDujY >>271 >（一階述語のZFC vs 圏論（二階述語）かも） 追加参考 https://researchmap.jp/hisashi-aratake/ 荒武 永史 https://researchmap.jp/hisashi-aratake/presentations 講演・口頭発表等 https://researchmap.jp/hisashi-aratake/presentations/41535386/attachment_file.pdf 圏論的論理学の拡がり 荒武永史 京都大学数理解析研究所 2023 年2 月23 日 Logic Winter School 2023 P5 トポスにおける数学 トポスを“集合の宇宙”と見なして内部論理で数学を展開する ・ 高階論理（型付き！）で表現できる範囲という制限はつく ・ 排中律や選択公理は成り立つとは限らない 構成的数学と相性がいいが、非可述的な操作（分離公理, 冪など）も許さ れる。近年では可述的トポスの研究も進められている。 https://researchmap.jp/hisashi-aratake/presentations/41535371 高階直観主義論理とトポス 荒武永史 ロジックウィンタースクール2023 2023年2月22日 http://rio2016.5ch.net/test/read.cgi/math/1687778456/273
340: １３２人目の素数さん [] 2023/07/04(火) 17:54:34.28 ID:xZu413TU >>271-273 > ある分野やある手法に対しての > 加速定理を提供する能力が、 > 圏論にはあると思っています いかにも素人の誤った考え 圏論は「修辞」 > ゲーデルの加速定理： > 弱い形式的体系では非常に長い形式的証明しか存在しないが、 > より強い形式的体系では極めて短い形式的証明が存在する 圏論が「より強い体系」だと思うのは誤解 > ここまでは、期待できるかも。ある分野では 全然 > 層の理論も、一種の加速定理と思っています まったく誤解 層はファイバー束の一般化 なにも加速していない ブルバキがいうところの形式主義は「修辞」 例えば線形代数や位相の理論が 一種の加速定理とかいうなら 思いっきり誤解 線形代数を圏に置き換えたところで 偽が真になるわけではない >>274 >>n階算術の体系で証明可能な命題であって、 >>n+1階算術ではより短い証明を持つものが存在する > n階算術の体系の証明可能な命題の証明の長さは > n→∞のとき有界であるとは思えない。 ω階算術も形式的体系だから そんなことが可能なら ゲーデルの不完全性定理が否定される >>275 > ∞カテゴリーかな 万能の魔法など存在せぬ ありもせぬ「賢者の石」を求めるのは究極の愚か者 さて、おサルでも知ってる、 ライプニッツの明示公式による行列式の計算時間 を行列のサイズnのオーダーで表すとO(n!) 一方、 ガウスの消去法による行列式の計算時間 を行列のサイズnのオーダーで表すとO(n^3/3) これを以て、 「線形代数が行列の正則性（あるいは行ベクトルの一次独立性）の証明を加速した」 というヤツは、愚か者 １が言ってるのはそんな人間失格のおサルレベル http://rio2016.5ch.net/test/read.cgi/math/1687778456/340
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.041s