史上最も難しい論理パズル

史上最も難しい論理パズルは、アメリカの哲学者で論理学者のジョージ・ブーロスが名付けた論理パズルで、1996年にハーバード哲学評論誌^{に掲載された。 [1] [2]}ブーロスの記事には、問題を解く方法が複数含まれている。イタリア語への翻訳は、以前、新聞「ラ・レプブリカ」に「世界で最も難しいインドヴィネッロ」というタイトルで掲載された。

それは次のように述べられています。

3 人の神 A、B、C は、順不同で、真、偽、ランダムと呼ばれます。真は常に真実を語り、偽は常に偽りを語りますが、ランダムが真実を語るか偽りを語るかは完全にランダムです。あなたの仕事は、3 つのyes-no の質問をして、A、B、C の正体を突き止めることです。各質問は、正確に 1 人の神に対して行わなければなりません。神々は英語を理解しますが、すべての質問に、yesとnoがdaとjaである独自の言語で答えます^[3]。どの単語が何を意味するかはわかりません。

ブーロスは次のような説明をしている。^[1]一人の神に複数の質問がなされる可能性があり、質問は以前の質問への回答に依存することが許されており、ランダムの応答の性質は彼の脳内に隠された公平なコインを投げることに依存すると考えられるべきである。コインが表が出れば彼は真実を語り、裏が出れば偽りを語る。^[4]

ブーロスは、このパズルの考案者は論理学者レイモンド・スマリヤンであり、daとjaの意味が分からないという難しさはジョン・マッカーシーが付け加えたとしている。スマリヤンの著作には、関連するパズルが随所に見られる。例えば、「この本の名前は何か?」^[5]では、住民の半分がゾンビ (いつも嘘をつく) で、半分が人間 (いつも本当のことを言う) であるハイチの島について説明している。彼は、「原住民は全員英語を完璧に理解しているが、島の古いタブーにより、会話で非ネイティブの単語を使うことは禁じられているため、状況は非常に複雑になっている。そのため、イエスかノーかで答える質問をすると、彼らはBalまたはDaと答える。どちらかがイエス、もう片方がノーを意味する。問題は、BalとDaのどちらがイエスでどちらがノーを意味するのかわからないことだ」と説明している。「シェヘラザードの謎」には、関連するパズルが他にもある。^{[6] [7]}

このパズルは、騎士と悪党のパズルに基づいています。このパズルの舞台の 1 つは、騎士と悪党だけが住む架空の島です。そこでは、騎士は常に真実を語り、悪党は常に嘘をつきます。島を訪れた人は、必要な情報を得るために、いくつかの「はい/いいえ」の質問をする必要があります (詳細は、パズルのバージョンによって異なります)。このパズルの 1 つのバージョンは、1986 年のファンタジー映画「ラビリンス」のシーンで有名になりました。ドアが 2 つあり、それぞれに 1 人の警備員がいます。1 人の警備員は常に嘘をつき、もう 1 人の警備員は常に正直に答えます。1 つのドアは城に通じ、もう 1 つのドアは「確実な死」に通じています。このパズルは、警備員の 1 人に 1 つの質問をして、どのドアが城に通じているかを突き止めるというものです。映画では、主人公は「彼 [もう 1 人の警備員] は、このドアが城に通じていると私に言うでしょうか?」と質問することでこれを行います。

Boolos は、このパズルを紹介した同じ記事で、その解答も示しています。Boolos は、「最初の動きは、ランダムではない、つまり真か偽かのいずれかであると確信できる神を見つけることです」と述べています。^[1]この結果を達成する質問は多種多様です。1 つの戦略は、質問に複雑な論理接続詞 (双条件文または同等の構造) を使用することです。

Boolos の質問は A に尋ねるものでした。

daは、あなたがTrueの場合のみ、BがRandomの場合のみ、yesを 意味しますか？ ^[1]

同様に:

次の文の奇数は真ですか: da は「はい」を意味し、you は「真」、B は「ランダム」ですか?

ロバーツ（2001）とラバーンとラバーン（2008）は独立して、このパズルの解決法は特定の反事実的仮定を用いることで簡略化できることを観察した。^{[6] [8]}この解決法の鍵は、どんなはい/いいえの質問Qに対しても、質問が真か偽かのどちらかであるかどうか尋ねると、

Qと聞かれたら、jaと答えますか？

Q に対する真の答えが「はい」の場合、答えjaが返され、Q に対する真の答えが「いいえ」の場合、答えda が返されます(Rabern と Rabern (2008) はこの結果を埋め込み質問補題と呼んでいます)。これが機能する理由は、質問に対する予想される答えの論理形式を調べることでわかります。この論理形式 (ブール式) は以下のように展開されます (「Q 」は、 Q に対する答えが「はい」の場合に真、「神」は、質問された神が真実を語る者として行動している場合に真、「Ja」は、 Jaの意味が「はい」の場合に真です)。

1. 神が Q にどう答えるかは、 Qと神との排他的論理和の否定によって決まります(Q に対する答えと神の性質が反対であれば、神の答えは必ず「いいえ」になり、同じであれば必ず「はい」になります)。
   • ¬ ( Q ⊕ 神)
2. 神が与えた答えがJaであるかどうかは、前の結果とJaの間の排他的論理和の否定によって再び与えられる。
   • з ( ( з ( Q ⊕ 神) ) ⊕ Ja )
3. ステップ2の結果は、「私があなたにQと尋ねたら、あなたはjaと答えますか？」という質問に対する本当の答えを与えます。神が与える答えが何であるかは、ステップ1で使用したのと同様の推論を使用して確認することができます。
   • з ( ( з ( ( з ( Q ⊕ 神) ) ⊕ Ja ) ) ⊕ 神 )
4. 最後に、この答えがJaかDaかを調べるには、ステップ3の結果と Jaの排他的論理和の（さらにもう一つの）否定が必要になります。
   • з ( ( з ( ( з ( ( з ( Q ⊕ 神) ) ⊕ Ja ) ) ⊕ 神 ) ) ⊕ Ja )

この最後の式は、答えがJaの場合は true 、それ以外の場合は false と評価されます。8 つのケースは以下のように処理されます (1 は true、0 は false を表します)。

最初の列と最後の列を比較すると、質問の答えが「はい」の場合にのみ、答えが Ja であることがはっきりとわかります。代わりに「私が Q と尋ねたら、Da と答えますか?」と質問された場合も同じ結果が適用されます。これは、反事実の評価が表面的にはJaとDaの意味に依存しないからです。8つのケースはそれぞれ、次のように言葉で説明できます。

• ja はyesを意味し、da はnoを意味するものとします。

1. True が質問され、jaと答えます。彼は真実を語っているので、 Q に対する本当の答えはja、つまりyesです。
2. True が質問され、 daと答えます。彼は真実を語っているので、 Q に対する本当の答えはda、つまり「いいえ」です。
3. False と尋ねられ、jaと答えます。彼は嘘をついているので、 Q と尋ねられた場合、彼はdaと答えるはずです。彼は嘘をついているので、 Q に対する本当の答えはja、つまりyesです。
4. False と尋ねられ、daと答えます。彼は嘘をついているので、 Q と尋ねられた場合、実際にはja と答えることになります。彼は嘘をついているので、 Q に対する本当の答えはda、つまり「いいえ」です。

• ja はnoを意味し、da はyesを意味するものとします。

1. True が尋ねられ、 jaと答えます。彼は真実を語っているので、 Q に対する本当の答えはda、つまりyesです。
2. True が尋ねられ、 daと答えます。彼は真実を語っているので、 Q に対する本当の答えはja、つまり「いいえ」です。
3. False と尋ねられ、jaと答えます。彼は嘘をついているので、 Q と尋ねられた場合、彼は実際にja と答えることになります。彼は嘘をついているので、 Q に対する本当の答えはda、つまりyesです。
4. False と尋ねられ、daと答えます。彼は嘘をついているので、 Q と尋ねられた場合、彼はdaと答えるはずです。彼は嘘をついているので、 Q に対する本当の答えはja、つまり「いいえ」です。

質問された神が嘘をついているか否かに関わらず、またどの単語が「はい」を意味し、どの単語が「いいえ」を意味するかに関わらず、 Q に対する真実の答えが「はい」か「いいえ」かを判断できます。

以下の解答は、上記の補題を用いて3つの質問を構築している。^[6]

Q1: 神 B に「私があなたに「A はランダムですか?」と尋ねたら、ja と答えますか?」と尋ねます。B がjaと答えた場合、B はランダム (ランダムに答えている) であるか、B はランダムではなく、答えは A がランダムであることを示しています。いずれにしても、C はランダムではありません。B がda と答えた場合、B はランダム (ランダムに答えている) であるか、B はランダムではなく、答えは A がランダムではないことを示しています。いずれにしても、ランダムではない神の正体がわかります。

Q2:前の質問 (A または C) でランダムではないと特定された神のところに行き、次のように尋ねます。「私があなたに「あなたは偽ですか?」と尋ねたら、あなたは「ja」と答えますか?」彼はランダムではないので、daの答えは彼が真であることを示し、 jaの答えは彼が偽であることを示します。

Q3: 同じ神に「もし私があなたに『B はランダムですか?』と尋ねたら、あなたはja と答えますか?」と質問します。答えがjaの場合、B はランダムです。答えがdaの場合、まだ話していない神はランダムです。残りの神は消去法で特定できます。

ブーロスの3番目の説明では、ランダムの行動を次のように説明しています。^[6]

ランダムが真実を語っているかどうかは、彼の脳内に隠されたコインを投げて結果が決まると考えるべきです。コインが表なら彼は真実を語り、裏なら嘘を語ります。

これは、コイン投げが各質問に対してなのか、各「セッション」に対してなのか、つまり一連の質問全体に対してなのかは述べていません。セッションの期間中に続く単一のランダム選択として解釈すると、Rabern と Rabern は、Random からでも有用な回答を抽出できることを示しています。^[6]これは、回答者 (この場合は Random) が真実を語る人であるか偽りを語る人であるかに関係なく、Q に対する真実の回答が明らかになるように、反事実が設計されていたためです。

反事実に直面したときのランダムの行動の別の解釈は、彼が頭の中でコインを投げた後に質問全体に答えるが、質問がされている間に、以前の精神状態で Q の答えを思いつくというものです。もう一度言いますが、これによってランダムに反事実を尋ねることは無意味になります。これが事実であれば、上記の質問に少し変更を加えると、ランダムから常に意味のある答えを引き出す質問になります。変更は次のようになります。

もし私が今のあなたの精神状態でQと尋ねたら、あなたはjaと答えますか？^[6]

これにより、ランダムから真実を語る人と嘘をつく人の性格が効果的に抽出され、ランダムはそのうちの 1 人だけになります。こうすることで、パズルは完全に自明になり、真実の答えを簡単に得ることができます。ただし、ランダムは質問の正しい答えを決定する前に嘘をつくか真実を語るかを決めているものと想定されます。これは、パズルや説明文では述べられていません。

神Aに「もし私があなたに『あなたはランダムですか？』と今の精神状態で尋ねたら、あなたはそう答えますか？」 と尋ねます。

1. A がjaと答えた場合、A はランダムです: 神 B に「私があなたに「あなたは真実ですか?」と尋ねたら、あなたはja と答えますか?」 と尋ねます。
   • B がjaと答えた場合、B は真、C は偽となります。
   • B がda と答えた場合、B は False、C は True です。どちらの場合も、パズルは解けます。
2. A がda と答えた場合、A はランダムではありません。神 A に「私があなたに「あなたは真実ですか?」と尋ねたら、あなたはjaと答えますか?」 と尋ねます。
   • A がjaと答えた場合、A は True です。
   • A がda と答えた場合、A は False です。
3. 神 A に尋ねます。「私があなたに「B はランダムですか?」と尋ねたら、あなたは「はい」と答えますか?」
   • A がjaと答えた場合、 B はランダム、 C は A の反対になります。
   • A がda と答えた場合、 C はランダムであり、 B は A の反対です。

Boolos によって明らかにされた元の問題 (「コインが表になったら真実を語り、裏になったら嘘を語る」) を解決する過程で、質問をさらに変更することで、明示されていないとされる仮定に頼ることなく、真実の答えをエレガントに得ることができます。

もし私があなたに Q と尋ねて、あなたがこの質問に答えているのと同じくらい正直に答えるとしたら、あなたは「はい」と答えますか?

ここでの唯一の仮定は、ランダムが質問に答える際に、正直に答えている（「正直に話している」）か、または、偽りの答えをしている（「偽りの話をしている」）かのいずれかであり、これは明らかに Boolos の説明の一部です。このように、元の修正されていない問題（Boolos の説明付き）は、最もエレガントでシンプルに見える解決策を持つ「史上最も難しい論理パズル」であると考えられます。

ラバーンとラバーン（2008）は、ブーロスのオリジナルのパズルを修正して、ランダムが実際にランダムになるようにすることを提案しています。修正は、ブーロスの3番目の説明を次のように置き換えることです。^[6]

ランダムがjaと言うかdaと言うかは、彼の脳内に隠されたコインを投げた結果によって決まると考えるべきです。コインが表になったらjaと言い、裏になったらdaと言います。

この変更により、パズルを解くには、 「解決」セクションの先頭に示されている、より慎重な神の尋問が必要になります。

史上最も難しい論理パズルの簡単な解決法^[6]で、B. Rabern と L. Rabern は、このパズルのバリエーションを提案している。つまり、神はパラドックスに直面しても、jaもda も言わず、何も答えないというものである。たとえば、「この質問に、あなたの言語でno を意味する単語で答えますか?」という質問に True が答えると、神は正直に答えることができない。(この論文では、これを頭が爆発する場面で表現している。「...彼らは絶対的な神々です! 彼らにはただ 1 つの選択肢しかありません。頭が爆発するのです。」) 「頭が爆発する」ケースを認めることで、パズルのさらに別の解決法が与えられ、パズル (修正版とオリジナル版) を 3 つの質問ではなく 2 つの質問で解く可能性が生まれる。2 つの質問でパズルを解く方法を支持するために、著者らは 2 つの質問だけで同様のより簡単なパズルを解いている。

3 人の神 A、B、C は、順に、ゼファー、エウロス、アイオロスと呼ばれます。神々は常に真実を語ります。あなたの仕事は、はい/いいえの質問をして、A、B、C の正体を突き止めることです。各質問は、正確に 1 人の神に尋ねなければなりません。神々は英語を理解し、英語で答えます。

このパズルは 3 つの質問で簡単に解けることに注意してください。さらに、このパズルを 2 つの質問で解くには、次の補題が証明されます。

緩和された嘘つき補題。Aに「{[(この質問に「いいえ」と答えるつもりです) AND (B はゼファーです)] OR (B はユーラスです)} ですか?」と尋ねると、「はい」と答えれば B はユーラス、「いいえ」と答えれば B はアイオロス、頭が爆発すれば B はゼファーであることがわかります。したがって、1 つの質問で B の正体を判断できます。

この補題を使えば、2つの質問でパズルを解くのは簡単です。RabernとRabern (2008)は、同様のトリック（嘘つきのパラドックスを和らげる）を使用して、元のパズルを2つの質問だけで解きました。Uzquiano (2010)は、これらのテクニックを使用して、修正されたパズルに2つの質問の解決策を提供しました。^{[9] [10]}元のパズルと修正されたパズルの両方に対する2つの質問の解決策は、一部の神が特定の質問に答えることができないという事実を利用しています。次の質問には、TrueもFalseも答えることはできません。

「ドゥシャンベはキルギスタンにありますか？」という質問に対して、ランダムさんと同じように答えますか？

修正された Random は真にランダムな方法で答えるので、True も False も、Dushanbe がキルギスタンにあるかどうかという質問に対して Random がja と答えるかdaと答えるかを予測することはできない。この無知により、彼らは真実を言うことも嘘をつくこともできず、したがって沈黙するだろう。しかし、ランダムなナンセンスを吐き出す Random は、問題なくjaまたはdaを吐き出すだろう。Uzquiano (2010) はこの非対称性を利用して、修正されたパズルに 2 つの質問の解答を提供している。しかし、神々は「Random の脳内でコインを投げる前から Random の答えを予測する神託の能力」を持っていると仮定することもできるだろうか? ^[9]この場合、Rabern と Rabern (2008) で採用されているスタイルの自己言及的な質問を使用することで、2 つの質問の解答はまだ利用可能である。

この質問にdaと答えるかどうかという質問にja と答えますか?

ここでも、True も False も、それぞれ真実を語る、または嘘をつくという約束をしているため、この質問に答えることはできない。約束された答えがdaである場合に備えて、 jaと答えざるを得ないが、そうすることはできない。前と同じように、頭が爆発するだろう。対照的に、Random は無意味なことをつぶやき、ランダムにjaまたはdaと答える。Uzquiano (2010) もこの非対称性を利用して、修正されたパズルに 2 つの質問の解答を提供している。^{[9] [10]}しかし、Uzquiano 自身のパズルの修正では、Random が「ja」、「da」、または沈黙のいずれかに答えられるようにすることでこの非対称性を排除しているが、3 問未満では解くことができない。^[11]

• リチャード・ウェッブ。「3 人の神、3 つの質問: 史上最も難しい論理パズル」(ニューサイエンティスト、第 216 巻、第 2896 ～ 2897 号、2012 年 12 月 22 ～ 29 日、50 ～ 52 ページ)
• トム・エリス。史上最も難しい論理パズルよりもさらに難しい。
• ステファン・ウィンテイン。真実と遊ぶ。
• ウォルター・カルニエリ。 Contrafactuais, contradção eo enigma lógico mais difícil do mundo.レビスタオムニアルミナ。(ポルトガル語で)
• ジェイミー・コンドリフ。史上最も難しい論理パズル（およびその解き方）。
• 史上最も難しい論理パズル (Googlesites ページ)