形式的体系に関する加速定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/04 01:50 UTC 版)
「加速定理」の記事における「形式的体系に関する加速定理」の解説
理論 T {\displaystyle T} とその拡大理論 S {\displaystyle S} について「 T {\displaystyle T} において証明可能な論理式で S {\displaystyle S} においてはより簡単に証明できるものが存在する」という形の定理は、計算複雑性に関する加速定理の類比として、同じく加速定理と呼ばれる。その代表的なものとしてはゲーデルの加速定理がある。これら異なるタイプの加速定理の間には或る種の対応が存在する。例えば、ブラムの加速定理の変種であるハルトマニスの加速定理を用いてゲーデルの加速定理が証明できることが知られている。また、エーレンフォイヒト・ミッシェルスキーの加速定理は、帰納的可算集合の加速可能性に関するある事実を用いて証明できる。
※この「形式的体系に関する加速定理」の解説は、「加速定理」の解説の一部です。
「形式的体系に関する加速定理」を含む「加速定理」の記事については、「加速定理」の概要を参照ください。
ウィキペディア小見出し辞書の「形式的体系に関する加速定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 形式的体系に関する加速定理のページへのリンク
