記述計算量 - Wikipedia
記述計算量（きじゅつけいさんりょう、英: Descriptive complexity）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、PHは二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。 特に、それぞれの論理体系は、その中で表現可能なクエリの集合を生み出す。クエリは計算複雑性理論における計算問題と対応している。 記述計算量の最初の成果として、1974年にロナルド・フェイギンが示した Fagin の定理がある[1]。これは、NPが存在量化二階
プログラマのための「ゲーデルの不完全性定理」(1) - 檜山正幸のキマイラ飼育記 (はてなBlog)
「プログラマのためのJavaScript」の番外シリーズ -- いやっ、ホントに。 これはシリーズのハブエントリーです。番号を（0じゃなくて）1にしたのは、全体目次だけじゃなくて内容が含まれるから。 ※ 印刷時にはサイドバーは消えるはずです、お試しください。 シリーズ全体目次（予定） （この記事；総論） 速攻速習編 自己適用からゲーデル化へ 「展望」への緊急パッチ（オハナシだよ） Reflective JavaScript 停止問題の構造 不完全性定理の構造 今回の内容： ゲーデルの不完全性定理とプログラミング ゲーデルが示したこと 不完全性定理の兄弟 -- 停止問題 JavaScript使うんだもんね 関連する記事（参考） 次の記事 速攻速習編 ●ゲーデルの不完全性定理とプログラミング 「ゲーデル」（人名；Kurt Godel、'o'の上に点々が付いてる）や彼の「不完全性定理」とかって、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
たまの雑記(2006-05-23)
２００６年数学基礎論サマースクール 限定算術の新展開 黒田覚（群馬県立女子大学） 2006/8/31–9/2 目 次 1 イントロダクション 1 2 計算量理論 2 2.1 基本概念など . . . . . . . . . . . . . . . . . . .
Whose Thesis is it Anyway?
The Importance of Natural Proofs
