論理学のクイズですが、次のクイズって結構難しいんです。
天国の門と地獄の門があり、各門に一人の門番がいます。どちらか一方が嘘だけを話す門番で、どちらか一方が真実だけを話す門番です。
正直者の門番も嘘つきの門番も見分けがつかなく、どっちの門の門番をしているかわかりません。
たった一つの質問をどちらかの門番にして、天国の門を通ることができるか？
答えは最後にということで、このクイズで思い出すのが嘘つきのパラドックスなんですが、その関係でちょっと面白いのが『ゲーデルの不完全性定理』です。
ゲーデルの不完全性定理には、第1不完全性原理と第2不完全性原理があります。
- 第1不完全性原理
「矛盾の無い理論体系の中に、肯定も否定もできない証明不可能な命題が必ず存在する」 - 第2不完全性原理
「理論体系に矛盾が無いとしても、その理論体系は自分自身に矛盾が無いことをその理論体系の中で証明できない」
ゲーデルが不完全性定理の証明に用いたのがゲーデル数と呼ばれるもので、コンピュータの世界でもなじみのあるものらしいです。ゲーデル数とは、記号や整論理式に割り振られる自然数ということですが、これだけだとなんのことかさっぱりなので、コンピュータを例にして簡単に説明してみます。
コンピュータはON、OFFといった2つの値の電気信号で動くのですが、これは0と1で対応できます。機械語は下記のような0と1の集まりです。
00000101 00000010
JavaScriptやPerlなどのプログラムは、最終的にこの機械語に変換されてコンピュータに処理を行わせているんですね。たとえば、「rhythm」という文字列も、コンピュータでは0と1の組み合わせで認識されています。ゲーデル数化とは、このように文字列に数字を対応させる事を指します。
チューリングの停止性問題
といった不完全性定理の後に発表されたのが、プログラム関連の書籍を読んでいるとたまに出現するチューリングの停止性問題。
停止性問題とは、ある機械に入力Xを入れたら、有限時間で停止するかという問題です。これをチューリングが、停止性問題を解く機械が存在しないという事を対角線論法で示しました。
これがちょっとわかりにくいので、嘘つきのパラドックスで説明します。
嘘つきのパラドックス
ということで、嘘つきのパラドックスに戻ってきてしまったのですが、それは以下のようなものです。
「クレタ人は嘘つきだ」とクレタ人が言った。
クレタ人自身が「クレタ人は嘘つき」と言及しているため、パラドックスが発生しているのですが、わかるでしょうか？
簡単に説明すると次のようになります。
・「クレタ人は嘘つきだ」が真実であれば、そのクレタ人も嘘つきです。とすると、そのクレタ人の「クレタ人は嘘つきだ」という発言も嘘になるので、そのクレタ人は正直者ということになります。
・「クレタ人は嘘つきだ」が嘘であれば、そのクレタ人は正直者ということです。とすると、そのクレタ人の「クレタ人は嘘つきだ」が真実になってしまうので、そのクレタ人は嘘つきということになります。
というパラドックスです。このようなパラドックスを自己言及のパラドックスと呼びます。ちなみに、この発言をしたクレタ人とされているのがエピメニデスというギリシャの伝説的な預言者です。
集合論におけるパラドックス
嘘つきのパラドックスはとてもわかりやすいのですが、より完全に近いパラドックスとして「この文は間違っている」、「集合論におけるパラドックス」などがあります。なかでも、個人的には集合論におけるパラドックスが好きでして、プログラマであればちょっとなじみがあって面白いと思います。
まず、全ての集合を2種類に分類します。ひとつは、自分自身を要素として含む集合Aで、もうひとつは自分自身を要素として含まない集合Bです。
「自分自身をその要素として含まない集合」の具体例をあげると、「丸いものの集合」や「赤いものの集合」のような、集合それ自体が丸いものではない、赤いものではない集合のことです。「自分自身をその要素として含む集合」とは、「不可視物体の集合」や「無生物の集合」といった、集合それ自体が自身の要素の条件としてあげる条件に合う集合のことです。
ここで、集合Aの集合を集合AXとした場合、集合AXも集合なので集合Aか集合Bに分類する必要があります。
集合AXが集合Aに分類できると仮定すると、集合AXは自分自身を要素に含みません。しかし、集合AXは集合Aの集合でもあるので、集合AXは集合Aに含まれる自分自身を要素にすることになり、矛盾となります。
集合AXが集合Bに分類できると仮定すると、集合AXは自分自身を要素に含みます。しかし、集合AXは集合Aしか含んでいなので、集合Aの条件から集合AXの要素となることはなく、矛盾となります。
以上から、集合AXを集合Aと仮定しても、集合Bと仮定しても矛盾が生じます。
これらのパラドックスは特に実用性があるわけでもないのですけれども。
答え
クイズの答えですが、それは次の質問になります。
隣の門の門番は、その門が天国の門と地獄の門、どちらだと答えますか？
嘘と真実を相殺させているのですが、まずは隣の門番が嘘つきの場合を想定して話を進めてみましょう。
・嘘つきの隣の門番が「天国の門」だと答えた場合、目の前の正直者の門番は「地獄の門」だと答えたはずです。
次に、隣の門番が正直者の場合。
・正直者の隣の門番が「天国の門」だと答えた場合、目の前の嘘つきの門番は嘘をついて「地獄の門」だと答えたはずです。
ということで、目の前の門番が地獄の門だと答えた方を通れば天国に行ける、ということです。