| ホーム ＞ 結城浩の日記 ＞ Goedel is the last name of Kurt... | 検索 | 更新情報 |
|
|
|
解答
言えない。 反例は「NDSNDS」。
以下、NDSNDSのカードはスキャナを通らないが有効なカードであることを証明する。
ルール(d)により、
「NDSNDSが有効である」⇔「NDSNDSのカードがスキャナを通らない」
である。したがって、次の(A)(B)のいずれかが真となる。
ところで、(B)はルール(f)と矛盾する。 したがって(A)が成り立つ。
解説
意味論的に書いてみましょう。
つまりこのシステムでは、カードに書かれている文字列によって、 有効なカードは何であるかを記述できることになります。
「NDSNDS」というのは「NDSを2回繰り返したものがスキャナを通らない」という命題です。 つまり「自分はスキャナを通らない」という命題になっているのですね。 これはカントールの対角線論法や、計算機の停止問題と類似した考え方です。
ゲーデルはこれと似た議論を展開して不完全性定理を証明しました。 「あるカードがスキャナを通る」というのを「ある文が証明可能である」に置き換え、 「あるカードが有効である」というのを「ある文が真である」に置き換えます。 すると「真であるのに証明が不可能な文が存在する」ということが言えることになります。
以下余談。 KurtくんはLedeog Universityの研究者、と4月1日の日記で書きましたが、 LedeogというのはGoedelの逆綴りです。 また、Kurtというのはゲーデルの名前です。
解答
「有効なカードはすべてこのスキャナを通る」とは言えない。
「有効なのにスキャナを通らないカード」として、
文字列 "NDSNDS" を持つカードが存在する。
この解答を得た過程を以下に示す。
[ルール]
以降において、カードが持つ文字列のタイプを「Card」と記述する。
ある文字列 c がスキャナを通るかどうかの真理値を示す式を「S(c)」と、
有効であるかどうかの真理値を示す式を「V(c)」と記述する。
記号「+」は文字列の連結を表す。
ルール(a) (∀c : Card |: S(c) ≡ V("S" + c) ) が成り立つ
ルール(b) (∀c : Card |: ¬S(c) ≡ V("NS" + c) ) が成り立つ
ルール(c) (∀c : Card |: S(c + c) ≡ V("DS" + c) ) が成り立つ
ルール(d) (∀c : Card |: ¬S(c + c) ≡ V("NDS" + c) ) が成り立つ
ルール(e) (∀c : Card | S(c) : V(c) )
= (∀c : Card |: S(c) ⇒ V(c) ) が成り立つ
ルール(f) (∀c : Card | ¬V(c) : ¬S(c) )
= (∀c : Card |: ¬V(c) ⇒ ¬S(c) )
= (∀c : Card |: S(c) ⇒ V(c) ) が成り立つ
つまり、(e) と (f) は同値。
[問題]
(q) (∀c : Card |: V(c) ⇒ S(c) ) が成り立つか？
[解答1]
以下に反例を示す。
(e) より、
(e') S("NDSNDS") ⇒ V("NDSNDS") が成り立つ。
(d) より、
(d'') ¬S("NDS" + "NDS") ≡ V("NDS" + "NDS")
= ¬S("NDSNDS") ≡ V("NDSNDS")
= S("NDSNDS") ≡ ¬V("NDSNDS") が成り立つ。
(e') より、
(e'') S("NDSNDS") ⇒ V("NDSNDS")
= ¬V("NDSNDS") ⇒ V("NDSNDS")
= ¬V("NDSNDS") ∧ V("NDSNDS") ≡ ¬V("NDSNDS")
= V("NDSNDS") ≡ true
= S("NDSNDS") ≡ false が成り立つ。
従って、文字列 "NDSNDS" を持つカードは有効であるが
スキャナを通らない。 □
[解答2]
以下に (q) が成り立たないことを示す。
(q) が成り立つならば、(e) より
(q') (∀c : Card |: S(c) ≡ V(c) )
が成り立つ。
(q')が成り立つならば、
(q'') S("NDS" + "NDS") ≡ V("NDS" + "NDS")
が成り立つ。
一方、(d) より
(d') !S("NDS" + "NDS") ≡ V("NDS" + "NDS")
が成り立つ。
しかし (q'') と (d') は矛盾する。
従って (q) は成り立たない。 □
今回のパズルの題材は以下の本から得ています。