翻訳と辞書 Words near each other ・ ゲーテ大学 ・ ゲーテ学院 ・ ゲーテ街道 ・ ゲーテ賞 ・ ゲーデ ・ ゲーディ ・ ゲーデル ・ ゲーデル、エッシャー、バッハ ・ ゲーデル、エッシャー、バッハ - あるいは不思議の環 ・ ゲーデルの不完全性定理 ・ ゲーデルの加速定理 ・ ゲーデルの完全性定理 ・ ゲーデルン ・ ゲーデル数 ・ ゲーデル数化 ・ ゲーデル解 ・ ゲーデル賞 ・ ゲート ・ ゲート オブ サンダー ・ ゲート 自衛隊 彼の地にて、斯く戦えり Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ゲーデルの加速定理 ： ミニ英和和英辞書 ゲーデルの加速定理[げーでるのかそくていり] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] 　(n) long vowel mark (usually only used in katakana) ・ 加 ： [か] 　【名詞】 1. addition　2. increase　 ・ 加速 ： [かそく] 　【名詞・動詞】acceleration, accelerate ・ 定理 ： [ていり] 　【名詞】 1. theorem　2. proposition ・ 理 ： [り] 　【名詞】 1. reason　 ゲーデルの加速定理 ： ウィキペディア日本語版 ゲーデルの加速定理[げーでるのかそくていり] ゲーデルの加速定理（ゲーデルのかそくていり、）はで証明された。この定理によれば、弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する、というような文が存在する。 クルト・ゲーデルはそのような性質を持つ文を具体的に構成した。それはn階算術の体系で証明可能な命題であってn+1階算術ではより短い証明を持つものが存在するというものである。類似の例として最短の形式的証明がとてつもなく長大となる文を構成しよう。形式化された対角線論法によって :φ「この文は高々グーゴルプレックス個の記号からなる（ペアノ算術からの）形式的証明を持たない」 なる内容的意味を持つ文を構成する。（ここで「グーゴルプレックス個の記号からなる」という部分を取り除くと不完全性定理の決定不能な文が得られる。）コーディングを工夫すれば φ がΣ1論理式となるようにできる。φ はペアノ算術から証明可能である：もし証明不能なら「高々グーゴルプレックス個の記号からなる（ペアノ算術からの）形式的証明を持たない」が標準模型で真なので、Σ1完全性より φ は証明可能である。これは不合理。したがって φ は証明可能である。するとΣ1健全性より φ は標準模型で真である。つまり「φ は高々グーゴルプレックス個の記号からなる（ペアノ算術からの）形式的証明を持たない」から、φ の形式的証明はグーゴルプレックス個よりも多くの記号から構成される。〔もっとも、この場合は文そのものにとてつもなく長大な数字（グーゴルプレックス）が埋め込まれているので、それが原因で証明が長くなってしまっている可能性を排除できない。〕 φはより強い体系ではもっと短い形式的証明を持つ：例えばペアノ算術に自身の無矛盾性を表す公理 Con(PA) を追加した体系を用いればよい。（追加された公理は不完全性定理よりペアノ算術からは証明不能である。）すると上の背理法による議論を体系内で実行することでより短い形式的証明が得られる： ¬φ と仮定する。ここから ProvablePA(φ) を得る。他方で ¬φ に形式化されたΣ1完全性を適用すれば ProvablePA(¬φ) を得る。ここに形式化されたモーダス・ポネンスを適用すれば ProvablePA(⊥) すなわち ¬Con(PA) を得る。公理 Con(PA) とモーダス・ポネンスによって矛盾 ⊥ を得る。背理法によって（仮定なしで） φ を得る。 以上の議論のペアノ算術は別のより強い無矛盾な体系に置き換えられる。またグーゴルプレックスもその体系で記述できる別の任意の数字に置き換えられる。 ハービー・フリードマンは上の性質を満たすような明示的で自然な例をいくつか見つけた。それはペアノ算術やほかの形式的体系における文であり、その最短の証明は非常に長い。 == エーレンフォイヒト・ミッシェルスキーの加速定理 == 帰納的理論 $T$ と文 $\backslash varphi$ について $T+\backslash neg\backslash varphi$ は決定不可能であると仮定する。したがってとくに $\backslash varphi$ は $T$ で証明できない。いま $T+\backslash varphi$ で証明できて $T$ で証明できない文の全体を $D$ とおく。すると :$\backslash varphi\; \backslash vee\; \backslash psi\; \backslash in\; D\; \backslash iff\; T\; \backslash not\backslash vdash\; \backslash varphi\; \backslash vee\; \backslash psi\; \backslash iff\; T+\backslash neg\backslash varphi\; \backslash not\backslash vdash\; \backslash psi$ となる。したがって $D$ は帰納的可算でない。ただしd-帰納的可算ではある。 $T$ における証明と $T+\backslash varphi$ における証明の複雑性を比較したい。ただし証明の複雑性を測る関数 $|\backslash cdot|$ はstatic complexity measureの条件を満たすものとする。理論 $S$ における文 $\backslash psi$ の証明の複雑さの最小値を $\backslash Vert\backslash psi\backslash Vert\_S$ と書くことにする。エーレンフォイヒトとミッシェルスキーは次の加速定理を証明した：任意の計算可能関数 $r$ に対して、$T$ で証明可能な文 $\backslash psi$ が存在して $r(\backslash Vert\backslash psi\backslash Vert\_)\; \backslash leq\; \backslash Vert\backslash psi\backslash Vert\_T$ が成り立つ。 いまこれが成立しないと仮定してみよう。すると、$T+\backslash varphi$ で証明可能な任意の文 $\backslash psi$ に対して、 : $T\; \backslash vdash\; \backslash psi\; \backslash implies\; r(\backslash Vert\backslash psi\backslash Vert\_)\; \backslash geq\; \backslash Vert\backslash psi\backslash Vert\_$ が成り立つ。したがって : $D\; =\; \backslash$ となるから、$D$ は帰納的可算である。これは上で示したことに反する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ゲーデルの加速定理」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.