不完全性定理について(あるいは証明と計算について)

「証明」という言葉と「計算」という言葉 「計算」という言葉の説明 「証明」という言葉の説明 ここまでのまとめ 補足:「完全」という言葉について 対角化定理と再帰定理 対角化定理 再帰定理 ラムダ計算との関係 第1不完全性定理、停止問題、その他 第1不完全性定理の証明 停止問題、真を表す述語の定義不可能性 自然数論の決定不能性 補足: 「決定可能」「決定不能」という言葉について 第2不完全性定理 第2不完全性定理の証明 第2不完全性定理の内容 補足: ヒルベルトの形式主義(ヒルベルト・プログラム) まとめ 文献 「証明」という言葉と「計算」という言葉 論理学についての話や説明をする場合、 「証明」とか「証明できる」という言葉がふたつの意味で使われる。 ひとつは数学とか日常で普通に使うのと同じ普通の意味での 「証明できる」(何かの正しさを筋道立てて示すことができる)で、 もうひとつは形式的な論

[usurausura]

対角化、再帰定理、不動点演算子

[nanakoso]

[

[tanimina]

消えているので代替→http://kreisel.fam.cx/webmaster/clog/img/www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/p/frag/frag_g.html

[tokyocat]

《「計算」という言葉に関して、「普通の計算」と「インタプリタのする計算」と「evalのする計算」とを区別できた。この区別が、すでに多少説明した「証明」の区別に対応する。 》

[mind]

不動点演算子Yの性質「Yf = f(Yf)」は 対角化定理や再帰定理と対応しているし、 演算子の定義「λf.(λx.f(xx))(λx.f(xx))」も 対角化定理や再帰定理の証明における式の構成方法に対応 ――任意の場面で ぐるぐる を召喚すれ@@!