[過去ﾛｸﾞ] ガロア第一論文と乗数イデアル他関連資料スレ5 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
272(1): 2023/07/03(月)07:09 ID:x5daDujY(2/5) AAS
>>271
つづき
形式的体系に関する加速定理
理論
T とその拡大理論
S について
「T において証明可能な論理式で S においてはより簡単に証明できるものが存在する」
という形の定理は、計算複雑性に関する加速定理の類比として、同じく加速定理と呼ばれる。
その代表的なものとしてはゲーデルの加速定理がある。
これら異なるタイプの加速定理の間には或る種の対応が存在する。
例えば、ブラムの加速定理の変種であるハルトマニスの加速定理を用いてゲーデルの加速定理が証明できることが知られている。[1]また、エーレンフォイヒト・ミッシェルスキーの加速定理は、帰納的可算集合の加速可能性に関するある事実を用いて証明できる。[2]
外部ﾘﾝｸ:ja.wikipedia.org
ゲーデルの加速定理
ゲーデルの加速定理（ゲーデルのかそくていり、英: Godel's speedup theorem）は、クルト・ゲーデル[1]により証明された、数理論理学における定理である。この定理によれば、弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する、というような文が存在する。より正確にいえば、それはn階算術の体系で証明可能な命題であって、n+1階算術ではより短い証明を持つものが存在するというものである。
(引用終り)
以上
340(1): 2023/07/04(火)17:54 ID:xZu413TU(4/15) AAS
>>271-273
> ある分野やある手法に対しての
> 加速定理を提供する能力が、
> 圏論にはあると思っています
いかにも素人の誤った考え
圏論は「修辞」
> ゲーデルの加速定理：
> 弱い形式的体系では非常に長い形式的証明しか存在しないが、
> より強い形式的体系では極めて短い形式的証明が存在する
圏論が「より強い体系」だと思うのは誤解
> ここまでは、期待できるかも。ある分野では
全然
> 層の理論も、一種の加速定理と思っています
まったく誤解
層はファイバー束の一般化
なにも加速していない
ブルバキがいうところの形式主義は「修辞」
例えば線形代数や位相の理論が
一種の加速定理とかいうなら
思いっきり誤解
線形代数を圏に置き換えたところで
偽が真になるわけではない
>>274
>>n階算術の体系で証明可能な命題であって、
>>n+1階算術ではより短い証明を持つものが存在する
> n階算術の体系の証明可能な命題の証明の長さは
> n→∞のとき有界であるとは思えない。
ω階算術も形式的体系だから
そんなことが可能なら
ゲーデルの不完全性定理が否定される
>>275
> ∞カテゴリーかな
万能の魔法など存在せぬ
ありもせぬ「賢者の石」を求めるのは究極の愚か者
さて、おサルでも知ってる、
ライプニッツの明示公式による行列式の計算時間
を行列のサイズnのオーダーで表すとO(n!)
一方、
ガウスの消去法による行列式の計算時間
を行列のサイズnのオーダーで表すとO(n^3/3)
これを以て、
「線形代数が行列の正則性（あるいは行ベクトルの一次独立性）の証明を加速した」
というヤツは、愚か者
１が言ってるのはそんな人間失格のおサルレベル
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.030s