計算モデルと論理とゲーデルの不完全性定理 - Gemmaの日記

ゲーデルの不完全性定理は、数学を扱う数学、つまりメタ数学を考えるが、それだと理解が難しい。しかし、証明(数学)＝プログラムという悟りを開くと、プログラムを扱うプログラム、つまりメタプログラムを考えればよくなり、それならコンパイラ等でなじみがあるので理解が優しくなる。 話の流れは以下。 1. プログラムとは何か 2. 証明とは何か 3. 証明＝プログラム , （ {、 { ヽ.ｰ､､ ＼､__ぃ._ゝ⌒ヾ iヾ）}､_ ﾝ_ｰ-_二ｰ-, 〉 {厶 _､ヽ _ ヽ._＞'´ ／ /,ィ／ / ハYﾍい ,. -- 〃⌒ r−-､ ィ´ 〃 ,ｲ/7' ,ｲイ/ 小ヽ 丶、 ,. ‐ '´ﾊ i ″｀ヽ、 、ヽ、 ／幺ィ {从{小込v' jｩ仏厶川ﾘ} YV, 小 Vj. |丶 ヽ ｀ ｰ-ミー--'_,辷三彡

[gologo13]

数学、論理、プログラムの絡めた解説。おもしろい

[nuc]

うおーうおーうおー、なんかいろいろ怪しい気がしてくるが、まあいいや。

[tanakaBox]

途中まで・・・

[nanto_vi]

証明 = プログラム。

[bigbro]

なんぞこれ！面白すぎる

[uyeee]

計算モデルと論理とゲーデルの不完全性定理

[Layzie]

難しいので俺には分かりませんが、シェリル！ということで後でちゃんと読む。

[osiire]

本人は分かってると思うのだけど、全ての入力でチューリング機械が停止する訳では無い事と、ある論理で真となる命題の中に証明可能でないものがある事をやや安直に結びつけすぎな気がする。この手の説明は難しい。

[kusigahama]

ふぐりむむじゅんってなんだ

[cho45]

タイトルから想像できない初まりだったので大いに吹きました

[uruloki]

きちんと理解しておきたい。何か本も読んでみよう。

[ystt]

「万能のウイルス発見プログラム」というのも停止性問題でよく挙げられる例ですね

[tomkosaka]

分かりやすい説明

[aont]

駒場の情報科学でプログラム停止問題と同じっていうのは聞いたことあるなぁ

[monopole]

チャイティンの「メタマス！」もこんな感じで説明してたよ(AAは出てきません)。

[kazutanaka]

チャイティンへの言及無し。思い出した。「知の限界」だ。

[charliecgo]

面白い。面白カテゴリなのはＡＡを多用しているからか？

[tanimina]

cf.→「不完全性定理について(あるいは証明と計算について) 」http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/p/frag/frag_g.html

[nanakoso]

数学基礎論＆プログラム意味論（概論）

[ICHIRO]

コレ系の講義で「D（不可）」取りました