「史上最も難しい論理パズル」は、アメリカの哲学者であり論理学者でもあるジョージ・ブーロスが1996年にハーバード哲学レビュー誌に掲載した論理パズルです。 [ 1 ] [ 2 ]ブーロスの論文には、この問題を解く複数の方法が記載されています。イタリア語への翻訳は、以前、新聞「ラ・レプッブリカ」に「L'indovinello più difficile del mondo(世界で最も難しいインド風パズル)」というタイトルで掲載されました。
それは次のように述べられています。
三柱の神 A、B、C は、順不同で、真、偽、ランダムと呼ばれます。真は常に真実を語り、偽は常に偽りを語りますが、ランダムが真実を語るか偽りを語るかは完全にランダムです。あなたの課題は、3 つの「はい」か「いいえ」で答える質問をして、A、B、C の正体を突き止めることです。各質問は、必ず一柱の神に尋ねなければなりません。神々は英語を理解しますが、すべての質問には、神々自身の言語で答えます。神々の言語では、「はい」と「いいえ」は「だ」と「じゃ」で、順序は決まっています。どの単語が何を意味するかは分かりません。
ブーロスは次のような説明をしている。[ 1 ]一人の神に複数の質問がなされることがあり、質問はそれ以前の質問への回答に依存することが許されており、ランダムの返答の性質は、彼の脳内に隠された公平なコインを投げて決まるものと考えられるべきである。コインが表が出れば彼は真実を語り、裏が出れば嘘を語る。[ 4 ]
ブーロスは、このパズルの考案者は論理学者レイモンド・スマリヤンであり、daとjaの意味が分からないという難しさを付け加えたのはジョン・マッカーシーであるとしている。スマリヤンの著作には、関連するパズルが随所に見られる。例えば、『この本の名前は?』[ 5 ]では、住民の半分がゾンビ(常に嘘をつく)で、残りの半分が人間(常に真実を語る)であるハイチの島について描写している。彼は次のように説明している。「原住民は皆英語を完璧に理解しているものの、島に古くからあるタブーにより、母国語以外の言葉を話すことが禁じられているため、状況は非常に複雑になっている。そのため、イエスかノーかを尋ねると、彼らはバルかダと答える。どちらかがイエス、どちらかがノーを意味する。問題は、バルとダのどちらがイエスで、どちらがノーを意味するのかわからないことだ。」『シェヘラザードの謎』にも、関連するパズルがいくつか登場する。[ 6 ] [ 7 ]
このパズルは「騎士と悪党」のパズルに基づいています。このパズルの舞台の一つは、騎士と悪党だけが住む架空の島です。そこでは、騎士は常に真実を語り、悪党は常に嘘をつきます。島を訪れる人は、知りたい情報を得るために、いくつかの「はい/いいえ」で答えられる質問をしなければなりません(質問の具体的な内容はパズルのバージョンによって異なります)。このパズルの一つのバージョンは、1986年のファンタジー映画『ラビリンス』のワンシーンで有名になりました。2つの扉があり、それぞれに1人の警備員がいます。1人の警備員は常に嘘をつき、もう1人は常に真実を答えます。1つの扉は城に通じ、もう1つの扉は「確実な死」に通じています。このパズルは、警備員の1人に質問をすることで、どちらの扉が城に通じているかを突き止めるというものです。映画では、主人公は「彼(もう1人の警備員)は、この扉が城に通じていると教えてくれるでしょうか?」と質問することで答えを見つけ出します。
ブーロスは、このパズルを紹介した同じ記事の中で、その解答を提示しました。ブーロスは、「まず最初にすべきことは、ランダムではない、つまり真か偽かのいずれかであると確信できる神を見つけることだ」と述べています。[ 1 ]この結果を達成できる質問は数多くあります。一つの戦略としては、質問に複雑な論理接続詞(二条件文またはそれと同等の構文) を用いることが挙げられます。
Boolos の質問は A に尋ねるものでした。
日常言語では、この文はほとんど理解できません。論理学の用語では、「もし~ならば」とは、「2つの命題は同じ真理値を持つか?」という意味です。つまり、この文は次のような論理的つながりを表現しようとしているのです。
(da = はい) NXOR (あなたは True) NXOR (B はランダム)。
別の表記法を使用すると(⊕はXOR、¬はNOTを意味します):
(da = はい) ¬⊕ (あなたは真実です) ¬⊕ (B はランダムです)。
論理的に同等なのは次の文で、日常言語でより理解しやすいものです。
ロバーツ(2001)とラバーンとラバーン(2008)は、このパズルの解決法は、特定の反事実的仮定を用いることで簡略化できることを観察した。[ 6 ] [ 8 ]この解決法の鍵となるのは、どんなはい/いいえの質問Qに対しても、その質問に対して真か偽かを尋ねることである。
は、Qへの真の答えが「はい」の場合、答えは「 ja」となり、 Qへの真の答えが「いいえ」の場合、答えは「da」となります(RabernとRabern(2008)はこの結果を埋め込み質問補題と呼んでいます)。これは、他の「はい」と「いいえ」を表す表現にも適用できます。つまり、与えられた表現が繰り返される場合、Qへの答えは「はい」となり、そうでない場合は「いいえ」となります。これは、例えばフランス語を話す神に次のような質問をすることで、直感的に容易に理解できます。
True と False の両方が OUI と回答します。
これで、True と False の両方が NON と答えることになります。
どちらの場合も、TrueとFalseは質問で使用された単語を繰り返しています。これは、ローマが本当にイタリアにある場合にのみ行われます。別の答えは、ローマが他の場所にあることを意味します。OUIまたはNONをYES、NO、DA、JA(DAはロシア語で「はい」、JAはドイツ語で「はい」を意味します)などの他の単語に置き換えた場合も同様です。
これが機能する理由は、質問に対する期待される回答の論理形式を調べることでも明らかになります。この論理形式(ブール式)は以下のように展開されます(「Q」はQの回答が「はい」の場合に真、「神」は質問を受けた神が真実を語る者として行動している場合に真、「Ja」はJaの意味が「はい」の場合に真です)。
この最後の式は、答えがJaの場合に真、そうでない場合は偽と評価されます。8つのケースは以下のように解釈されます(1は真、0は偽を表します)。
| 質問 答えが真であれば Qは「はい」です | 神 神が行動するなら真実 真実を語る者として | じゃ 真の場合の意味 はい、そうです | ステップ1 (Qに対する神の答え) | ステップ2 (ジャですか?) | ステップ3 (反事実に対する神の答え) | ステップ4 (ジャですか?) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
最初の列と最後の列を比較すると、質問への答えが「はい」の場合のみ、答えがJaとなることが明らかです。 「もし私があなたにQと尋ねたら、あなたはDaと答えますか?」という質問でも同じ結果が当てはまります。なぜなら、反事実的評価はJaとDaの意味に表面的には依存しないからです。8つのケースはそれぞれ、以下のように言葉で等価に推論されます。
質問された神が嘘をついているか否かに関係なく、また、どの単語が「はい」を意味し、どの単語が「いいえ」を意味するかに関係なく、 Q に対する真実の答えが「はい」か「いいえ」かを判断できます。
以下の解答は、上記の補題を用いて3つの疑問を構成している。[ 6 ]
| 場合 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| あ | 真実 | 真実 | 間違い | ランダム | 間違い | ランダム | 真実 | 真実 | 間違い | ランダム | 間違い | ランダム | |||||
| B | 間違い | ランダム | 真実 | 真実 | ランダム | 間違い | 間違い | ランダム | 真実 | 真実 | ランダム | 間違い | |||||
| C | ランダム | 間違い | ランダム | 間違い | 真実 | 真実 | ランダム | 間違い | ランダム | 間違い | 真実 | 真実 | |||||
| ダ | はい | はい | はい | はい | はい | はい | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | |||||
| じゃ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | はい | はい | はい | はい | はい | はい | |||||
| Aは本当にランダムでしょうか? | いいえ | いいえ | いいえ | はい | いいえ | はい | いいえ | いいえ | いいえ | はい | いいえ | はい | |||||
| B は「A はランダムですか?」とどのように答えるでしょうか? | 英語 | はい | どちらか | いいえ | はい | どちらか | いいえ | はい | どちらか | いいえ | はい | どちらか | いいえ | ||||
| 彼らの言語 | ダ | どちらか | じゃ | ダ | どちらか | じゃ | じゃ | どちらか | ダ | じゃ | どちらか | ダ | |||||
| 質問 1 に対する B の回答 - 「「A はランダムですか?」と尋ねられたら、jaと答えますか?」」 | 英語 | はい | どちらか | はい | いいえ | どちらか | いいえ | いいえ | どちらか | いいえ | はい | どちらか | はい | ||||
| 彼らの言語 | ダ | どちらか | ダ | じゃ | どちらか | じゃ | ダ | どちらか | ダ | じゃ | どちらか | じゃ | |||||
| ダ | じゃ | ダ | じゃ | ダ | じゃ | ダ | じゃ | ||||||||||
| したがって、__ (以下、X と呼びます) はランダムではありません。 | あ | あ | C | あ | C | あ | C | C | あ | あ | C | あ | C | あ | C | C | |
| Xは本当にFalseですか? | いいえ | いいえ | はい | はい | はい | はい | いいえ | いいえ | いいえ | いいえ | はい | はい | はい | はい | いいえ | いいえ | |
| X は「あなたは偽者ですか?」にどのように答えますか? | 英語 | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ | いいえ |
| 彼らの言語 | じゃ | じゃ | じゃ | じゃ | じゃ | じゃ | じゃ | じゃ | ダ | ダ | ダ | ダ | ダ | ダ | ダ | ダ | |
| 質問 2 に対する X の回答 - 「『あなたは偽ですか?』と尋ねられたら、あなたはそう答えますか?」 | 英語 | はい | はい | いいえ | いいえ | いいえ | いいえ | はい | はい | いいえ | いいえ | はい | はい | はい | はい | いいえ | いいえ |
| 彼らの言語 | ダ | ダ | じゃ | じゃ | じゃ | じゃ | ダ | ダ | ダ | ダ | じゃ | じゃ | じゃ | じゃ | ダ | ダ | |
| したがって、X は __ です。 | 真実 | 真実 | 間違い | 間違い | 間違い | 間違い | 真実 | 真実 | 真実 | 真実 | 間違い | 間違い | 間違い | 間違い | 真実 | 真実 | |
| Bは本当にランダムですか? | いいえ | はい | いいえ | いいえ | はい | いいえ | いいえ | はい | いいえ | いいえ | はい | いいえ | |||||
| X は「B はランダムですか?」とどのように答えますか? | 英語 | いいえ | はい | いいえ | はい | はい | いいえ | はい | いいえ | いいえ | はい | いいえ | はい | はい | いいえ | はい | いいえ |
| 彼らの言語 | じゃ | ダ | じゃ | ダ | ダ | じゃ | ダ | じゃ | ダ | じゃ | ダ | じゃ | じゃ | ダ | じゃ | ダ | |
| 質問 3 に対する X の回答 - 「「B はランダムですか?」と尋ねられたら、そう答えますか?」」 | 英語 | はい | いいえ | いいえ | はい | はい | いいえ | いいえ | はい | いいえ | はい | はい | いいえ | いいえ | はい | はい | いいえ |
| 彼らの言語 | ダ | じゃ | じゃ | ダ | ダ | じゃ | じゃ | ダ | ダ | じゃ | じゃ | ダ | ダ | じゃ | じゃ | ダ | |
| したがって__はランダムです。 | C | B | B | C | あ | B | B | あ | C | B | B | C | あ | B | B | あ | |
| したがって、消去法によって、(文字) は (名前) になります。 | 手紙 | B | C | あ | B | B | C | あ | B | B | C | あ | B | B | C | あ | B |
| 名前 | 間違い | 間違い | 真実 | 真実 | 真実 | 真実 | 間違い | 間違い | 間違い | 間違い | 真実 | 真実 | 真実 | 真実 | 間違い | 間違い | |
上記と同様の表は、boolos によって提示された最初の質問が、結局のところ、Roberts と Rabern/Rabern の反事実的トリックと同じ効果と論理構造を持っていることを証明します。
ブーロスの3番目の説明では、ランダムの行動を次のように説明しています。[ 6 ]
ここでは、コイン投げが各質問に対して行われるのか、それとも各「セッション」に対して行われるのか、つまり一連の質問全体に対して行われるのかは明示されていません。セッション期間中続く単一のランダム選択として解釈すれば、RabernとRabernは、Randomからでも有用な回答を抽出できることを示しています。[ 6 ]これは、回答者(この場合はRandom)が真実を語る者であろうと虚偽を語る者であろうと、Qに対する真実の回答が明確になるように反 事実的条件が設計されていたためです。
反事実的状況に直面したランダムの行動について、別の解釈が考えられます。それは、彼が頭の中でコインを投げた後、質問全体に答えるが、質問がされている間に、以前の精神状態でQの答えを導き出すというものです。これもまた、反事実的状況についてランダムに尋ねることは無意味です。もしそうであれば、上記の質問を少し変更するだけで、ランダムから常に意味のある答えを引き出す質問が得られます。変更点は以下の通りです。
これは、ランダムから真実を語る者と嘘をつく者の人格を効果的に抽出し、彼をどちらか一方に押し込める。こうすることで、パズルは完全に自明になる。つまり、真実の答えは容易に得られる。しかし、これはランダムが問題の正解を決定する前に、嘘をつくか真実を語るかを決めていることを前提としている。これはパズルや説明文には明示されていない。
Boolos が明らかにしたように (「コインが表が出れば真実を語り、裏が出れば嘘を語る」)、元の問題を解決する過程で、明示されていないとされる仮定に頼ることなく、質問をさらに変更することで、真実の答えをエレガントに得ることができます。
ここでの唯一の仮定は、ランダムが質問に答える際に、真実に答えている(「真実を語っている」)か、偽りに答えている(「偽りを語っている」)かのいずれかであり、これはブーロスの明確化に明確に含まれています。このように、ブーロスの明確化を伴う元の修正されていない問題は、「史上最も難しい論理パズル」であり、最もエレガントでシンプルな解決策を持つと見なすことができます。
ラバーンとラバーン(2008)は、ブーロスの元のパズルを修正し、ランダムが実際にランダムになるようにすることを提案している。修正とは、ブーロスの3番目の説明を以下のものに置き換えることである。[ 6 ]
この変更により、パズルを解くには、 「解決」セクションの冒頭に示されている、より慎重な神の尋問が必要になります。
ブライアン・レイバーンとランドン・レイバーンは著書『史上最も難しい論理パズルの簡単な解答』[ 6 ] の中で、このパズルのバリエーションを提示している。神はパラドックスに直面しても「ja」とも「da」とも言わず、何も答えないというものである。例えば、「あなたはこの質問に、あなたの言語で「ノー」を意味する単語で答えますか?」という質問に「True」と答えても、彼は正直に答えることができない。(この論文ではこれを彼の頭が爆発する場面で表現し、「…彼らは絶対的な神々だ!彼らにはただ一つの頼みの綱、頭が爆発するしかないのだ」と述べている。)「頭が爆発する」というケースを許容することで、このパズルのさらに別の解答が得られ、3問ではなく2問だけでパズル(修正版とオリジナル版)を解く可能性が生まれる。この2問で解けるというパズルの解決策を支持するため、著者らは2問だけで似たようなより簡単なパズルを解いている。
このパズルは3問で自明に解けることに注意してください。さらに、このパズルを2問で解くには、次の補題が証明されます。
この補題を用いると、パズルを2問で解くのは簡単です。RabernとRabern (2008)は、同様のトリック(嘘つきのパラドックスの緩和)を用いて、元のパズルをたった2問で解きました。Uzquiano (2010)は、これらの手法を用いて、修正されたパズルを2問で解く解法を提供しています。[ 9 ] [ 10 ]元のパズルと修正されたパズルの両方に対する2問の解法は、一部の神が特定の質問に答えられないという事実を利用しています。次の質問には、TrueもFalseも答えることができません。
修正されたランダムは真にランダムな方法で答えるため、ドゥシャンベがキルギスタンにあるかどうかという質問に対して、トゥルーもフォルスもランダムがjaと答えるかdaと答えるかを予測できない。この無知ゆえに、彼らは真実を言うことも嘘をつくこともできず、したがって沈黙を守るだろう。しかし、ランダムなナンセンスを吐き出すランダムは、jaでもdaでも問題なく答えるだろう。ウズキアーノ(2010)はこの非対称性を利用して、修正されたパズルに2つの質問による解答を提供している。しかし、神々は「ランダムの脳内でコインを投げる前からランダムの答えを予言する神託の能力」を持っていると仮定することもできるかもしれない。[ 9 ]この場合、ラベルンとラベルン(2008)で用いられたスタイルの自己言及的な質問を用いることで、2つの質問による解答は依然として可能である。
ここでも、TrueとFalseはそれぞれ真実を語る、Falseは嘘をつくという約束をしているため、この質問に答えることができません。彼らは、約束された答えがdaだった場合に備えて、 jaと答えざるを得ませんが、そうすることはできません。以前と同じように、彼らは頭を爆発させてしまうでしょう。対照的に、Randomは無意識に意味不明なことを言い、ランダムにjaまたはdaと答えます。Uzquiano (2010)もこの非対称性を利用して、修正されたパズルに2問の解答を与えています。[ 9 ] [ 10 ]しかし、Uzquiano自身の修正は、Randomが「ja」、「da」、または沈黙のいずれかを選択できるようにすることでこの非対称性を排除していますが、3問未満では解くことができません。[ 11 ]
映画『マスターマインド』の冒頭シーンでは、このパズルを説明しようとする子供が登場します。