真に最難関の論理パズル

真に最難関の論理パズル（まさにさいなんかんのろんりパズル、The Hardest Logic Puzzle Ever）

とは、アメリカの哲学者で論理学者のがそう呼んでいた、1996年に「The Harvard Review of Philosophy」で掲載された論理パズルであるGeorge Boolos, 'The Hardest Logic Puzzle Ever'. The Harvard Review of Philosophy, Volume 6 (1996), pp.62-65 https://doi.org/10.5840/harvardreview1996615. 。問題を解決する複数の方法がブーロスの論説にあり、イタリア語翻訳が「世界で最も危険なパズル」というタイトルで、新聞ラ・レプッブリカに掲載された。

その問題とは以下の通り。

 3柱の神様A、B、Cは、それぞれ誰かが真、偽、ランダムです。真は必ず真実の答えを、偽は必ず嘘の答えを言いますが、ランダムが真実を答えるか嘘を答えるかは完全にランダムです。あなたは3つのをして、A、B、Cの正体（真か偽かランダム）を決めてください。1つの質問には1柱の神様しか答えてくれません（こちらで質問先A、B、Cの指定は可能）。神様は私たちの言葉を理解しますが、返答は私たちの言葉ではなく、神の言葉「Da」と「Ja」で返します。DaとJaのどちらがイエスでどちらがノーを意味するかは分かりません。

ブーロスは以下の注釈も付けている。単一の神様に複数の質問をしてもよい。前回質問の答えに依存した質問をしてもかまわない。ランダムの性質は彼の脳内に隠されている公正なコインを弾いた裏表に準じており、それが表側なら真実を語り、裏ならば嘘を語るブーロスのパズルにおけるランダム神は、真実の証人か嘘つきのどちらかとして、ランダムに行動する神であることに注意しなければならない。 これは無作為に「yes」または「no」と答える神とは異なる。多くの論理パズルを解決する一般的手口は、真実の証人と嘘つきの両方に「yes」と答えさせる質問（恐らく複合した）を設計することにある。そういった質問に対し、真実の証人か嘘つきかをランダムに選択した者は依然として「yes」と答えざるをえないが、無作為に答える人は「yes」または「no」と答えることがある。。

 歴史 
ブーロスは、論理学者のレイモンド・スマリヤンがこのパズルの創始者であり、ジョン・マッカーシーがdaとjaの意味を知らないという難しさを追加したと評している。関連するパズルはスマリヤンの著作から見つけることができる。例えば、『この本の名前は何？(What is the Name of This Book?)』の中で彼は、住民の半分がゾンビ（常に嘘つき）と半分が人間（常に真実を話す）であるハイチ島のパズル問題を書いている。彼はこう解説する「全ての原住民が英語を完全に理解しているにもかかわらず、島の古代のタブーで、彼らが非母国語を使ってしゃべることを禁じている状況が、非常に煩わしい。そのため、彼らにイエス・ノー質問をするたびに、彼らはBalまたはDaと答える。どちらか一方の意味はイエスで、他方がノーである。厄介なのは、BalかDaのどちらがイエスで、どちらがノーなのか分からない点である」。他の類似パズルは『シェヘラザードの謎かけ』にもあるRabern, B.; Rabern, L. (2008). "A simple solution to the hardest logic puzzle ever". Analysis. 68 (298): 105. doi:10.1111/j.1467-8284.2007.00723.x. 
。

今回のパズルは、騎士と悪党問題（Knights and Knaves）に基づいている。常に真実を伝える騎士と、常に嘘をつく悪党だけが住む架空の島という設定のパズルだ。 島の訪問者は、どうしても知る必要があるもの（出題の脚色により詳細は異なる）を発見するためにいくつかのイエスノー質問をしなければならない。これらパズルのあるバージョンは、1986年のファンタジー映画『ラビリンス/魔王の迷宮』によって大衆化された。守衛が2人いる2つのドアがある。 1人の守衛は嘘つきで、もう1人は違う。 1つのドアは城に通じており、もう1つは「確実な死」に導かれる。 そこでのパズルは、どちらの扉が城に通じているかを知るために、守衛のうち1人に1つだけ質問をするというもの。 映画の中で、主人公サラはこう尋ねている「彼（もう1人の守衛）は、このドアが城に通じていると私に教えてくれますか？」。

 解決法 
ブーロスは、パズルを紹介した同じ記事内に自身の解答を提示した。「最初にすることは、ランダムではないと確定できる神、つまり真か偽のどちらか、を見つけることだ」とブーロスは述べている。様々な質問でこの結果にはたどりつくだろう。1つの戦略としては、あなたの質問で複雑な論理接続（または同等構造のいずれか）を使うことにある。

ブーローズの質問はAに尋ねるもので、
もしBがランダムである場合で、もしあなたが真である場合なら、daはイエスという意味ですか？


ロバーツ(2001) そしてラベーン達 (2008) はそれぞれ独立に、ある種のを使ってパズルの解を単純化できることを見出した。これを解く鍵は、「任意のイエスノー質問Qに対して、その質問には真実または虚偽のどちらなのか」と尋ねることにある。

もし私があなたにQを尋ねたら、あなたはjaと言うでしょうか？

仮に、Qに対する真実の答えがイエスであれば答えはjaになり、Qに対する真実の答えがノーであれば答えはda（ラベーン達は、この結果を埋め込み質問の補題と呼ぶ）との結果をもたらす。こうなる理由は、質問に対して予想される答えのを研究することによって見えてくる。この論理形式（ブーリアン表現）は次のように展開される（もしQへの答えが「イエス」ならば「Q」は真、もし質問された神が真実の証人として行動するならば「神」は真、 もしJaの意味が「イエス」ならば「Ja」は真）。

どのようにして神がQに答えることを選ぶかは、Qと神との間における排他的論理和の否定により与えられる（仮にQへの答えと神の性質が反対であれば、神により与えられる答えは必ず「ノー」に縛られ、性質が同じならば必ず「イエス」になる）
¬ ( Q ⊕ God)
神により与えられる答えがJaか否かは、前の結果とJaとの間における排他的論理和の否定により再度与えられる。
¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja )
ステップ2の結果は、質問に対する真実の答えをもたらす。「私があなたにQを尋ねたら、あなたはJaと言うでしょうか？」 神が与えるだろう答えは、ステップ1で使ったのと同様の論法を使うことにより確認することが可能となる。
¬ ( ( ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) ) ⊕ God )
最後に、この答えがJaかDaかを明らかにするために、Jaとステップ3の結果との排他的論理和の否定（さらに別の）が必要とされる。
¬ ( ( ¬ ( ( ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) ) ⊕ God ) ) ⊕ Ja )

この最終表現は、仮に答えがJaの場合は真、それ以外は偽と評価する。以下8つのケースが生じる（1は真、0は偽）。

Qへの答えが
「イエス」の場合
Qは真神が真実の証人
として行動する場合
神は真Jaの意味が
「イエス」の場合
Jaは真Step 1
(Qに対する神の返答)Step 2
(それは「Ja」?)Step 3
(神の返答への
反事実的条件)Step 4
(それは「Ja」?)00010100011100010011001100001000101101001111010011111111

一番左と一番右の列を比較すると、質問に対する答えが「イエス」の場合にのみ、答えがJaであることがわかる。 代わりにこんな質問でも同じ結果が適用される「私があなたにQを尋ねたら、あなたはDaと言いますか？ 」。なぜなら、反事実的条件法の評価は、表面的にJaとDaの意味に依存しないからである。（ここで図示した） 8つのケースそれぞれは、下の言葉で等しく推論される。

jaがイエス、daがノーの意味だと仮定する。
真が尋ねられ、返答がja。彼は真実を語っているので、Qについて真実の答えはJa、これはイエスを意味する。
真が尋ねられ、返答がda。彼は真実を語っているので、Qについて真実の答えはda、これはノーを意味する。
偽が尋ねられ、返答がja。彼は嘘をついているので、あなたがQを彼に質問した場合に、彼はdaの代わりとして答えていることになる。彼は嘘をついているので、Qについて真実の答えはJa、これはイエスを意味する。
偽が尋ねられ、返答がda。彼は嘘をついているので、あなたがQを彼に質問した場合に、彼は実際にはjaと答えていることになる。 彼は嘘をついているので、Qについて真実の答えはda、これはノーを意味する。
jaがノー、daがイエスの意味だと仮定する。
真が尋ねられ、返答がja。彼は真実を語っているので、Qについて真実の答えはda、これはイエスを意味する。
真が尋ねられ、返答がda。彼は真実を語っているので、Qについて真実の答えはJa、これはノーを意味する。
偽が尋ねられ、返答がja。彼は嘘をついているので、あなたがQを彼に質問した場合に、彼は実際にはjaと答えていることになる。 彼は嘘をついているので、Qについて真実の答えはda、これはイエスを意味する。
偽が尋ねられ、返答がda。彼は嘘をついているので、あなたがQを彼に質問した場合に、彼はdaの代わりとして答えていることになる。 彼は嘘つきであり、Qについて真実の答えはJa、これはノーを意味する。

質問された神が嘘をついているかどうかに関係なく、どちらの言葉がイエスの意味でどちらがノーなのかにも関係なく、Qについての真実の答えがイエスかノーかを決定することが可能である。

下にある3つの質問の解決法は、上述の補題を利用した構成となっている。

Q1：神Bに尋ねます「私が「Aはランダムですか？」とあなたに尋ねたら、あなたはjaと言いますか？」。 
もしBがjaと答えれば、Bがランダム（無作為に答えている）か、もしくはBはランダムではなく、答えは実際にAがランダムということになる。いずれにせよ、Cは非ランダム。もしBがdaと答えた場合、Bがランダム（無作為に答えている）か、もしくはBはランダムではなく、答えは実際にAが非ランダムということになる。いずれにせよこの時点で、あなたは非ランダムな神を知っている。 
Q2：前の質問で非ランダムと識別できた神（AかCのどちらか）に行って、彼に尋ねます「もし私が「あなたは偽ですか？」と尋ねたら、あなたはjaと言いますか？」。
彼は非ランダムなので、daの答えは彼が真であることを示し、jaの答えは彼が偽であることを示す。この質問は「「da」は「イエス」を意味しますか？」に簡略化することもできる。
Q3：同じ神に質問します「私が「Bはランダムですか？」とあなたに尋ねたら、あなたはjaと言いますか？」。
答えがjaの場合、Bがランダム。答えがdaの場合、あなたがまだ話していない神がランダムである。残りの神は、消去法によって特定することができる。

以下がそのパターン図となる（便宜上、ランダムを「乱」と一部表記している。神の答えがランダムでイエス・ノー両方ともありうるケースは「両方」と表記）。
ケース 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16神A  真 真  偽  乱 偽  乱  真 真 偽  乱 偽  乱神B  偽 乱  真  真 乱  偽  偽 乱  真  真 乱  偽神C  乱 偽  乱  偽 真  真  乱 偽  乱  偽 真  真Daの意味  Yes Yes  Yes  Yes Yes  Yes  No No  No  No No  NoJaの意味  No No  No  No No  No  Yes Yes  Yes  Yes Yes  YesAは実際にランダムか? No No  No  Yes No  Yes  No No  No  Yes No  Yes「Aは乱か？」でのBの答え方  Yes/No  Yes 両方  No  Yes 両方  No  Yes 両方  No  Yes 両方  No  神言葉 Da 両方  Ja  Da 両方  Ja  Ja 両方  Da  Ja 両方  Da質問1にてBの返答あなたに「Aはランダムか？」と尋ねたら、答えは jaですか?  Yes/No  Yes 両方  Yes  No 両方  No  No 両方  No  Yes 両方  Yes神言葉Da 両方 Da Ja 両方 Ja Da 両方 Da Ja 両方 Ja Da  Ja  Da  Ja  Da  Ja  Da  Jaよって、__（以下X）は非ランダム A  A  C  A  C  A  C  C  A  A  C  A  C  A  C  CXは実際に偽か? No  No  Yes  Yes  Yes  Yes  No  No  No  No  Yes  Yes  Yes  Yes  No  No「あなたは偽か?」でのXの答え方  Yes/No  No  No  No  No  No  No  No  No  No  No  No  No  No  No  No  No  神言葉 Ja  Ja  Ja  Ja  Ja  Ja  Ja  Ja  Da  Da  Da  Da  Da  Da  Da  Da質問2にてXの返答もし「あなたは偽か?」と尋ねたら、答えはjaですか?  Yes/No  Yes  Yes  No  No  No  No  Yes  Yes  No  No  Yes  Yes  Yes  Yes  No  No 神言葉 Da  Da  Ja  Ja  Ja  Ja  Da  Da  Da  Da  Ja  Ja  Ja  Ja  Da  DaよってX は __.  真  真  偽  偽  偽  偽  真  真  真  真  偽  偽  偽  偽  真  真Bは実際にランダムか? No Yes  No  No Yes  No  No Yes  No  No Yes  No「Bは乱か?」でのXの答え方  Yes/No  No  Yes  No  Yes  Yes  No  Yes  No  No  Yes  No  Yes  Yes  No  Yes  No 神言葉 Ja  Da  Ja  Da  Da  Ja  Da  Ja  Da  Ja  Da  Ja  Ja  Da  Ja  Da質問3にてXの返答あなたに「Bはランダムか?」と尋ねたら、答えは jaですか?  Yes/No  Yes  No  No  Yes  Yes  No  No  Yes  No  Yes  Yes  No  No  Yes  Yes  No 神言葉 Da  Ja  Ja  Da  Da  Ja  Ja  Da  Da  Ja  Ja  Da  Da  Ja  Ja  Daよって __ がランダム. C  B  B  C  A  B  B  A  C  B  B  C  A  B  B  A消去法により、残る神と性質  残る神 B  C  A  B  B  C  A  B  B  C  A  B  B  C  A  B 性質 偽  偽  真  真  真  真  偽  偽  偽  偽  真  真  真  真  偽  偽

ランダムの行動
ブーロスの3つ目の注釈は、ランダムの行動を以下のように説明している。

ランダムが真実を話すかどうかは、脳に隠されたコイン弾きに応じて考えるべきである。コインの表側が来れば彼は真実を話し、裏側なら虚偽である。

果たして、コイン弾きは質問の度になのか、または「セッション」つまり一連の質問全体に対してなのか、が述べられていない。仮にセッションの最後まで単一のランダム選択が続いていると解釈した場合、2つの質問だけでこのパズルを解決できることをラベーン達は示している。これは、回答者 （この場合はランダム）が真実の証人なのか嘘つきなのかに関係なく、Qに対する真実の答えが明らかになるよう反事実的条件法が設計されているためである。

反事実的条件に直面した時のランダム行動のもう一つ可能な解釈として、彼は頭の中にあるコイン弾きをした後で全体の質問に返答するが、質問が尋ねられている間は、以前の心の状態でQに対する答えを出している、ということがある。これはもう一度、反事実的条件をランダムに尋ねることが無意味になる。仮にこの場合だと、上述の質問に対する小さな変更が、ランダムから常に有意義な回答を引き出す質問を生むようになる。変更は次のとおり。

もし私があなたの現在の精神状態であなたにQを尋ねたら、あなたはjaと言うでしょうか？

これは、ランダムから真実の証人と嘘つきの人格を効果的に引き出し、しかも彼にそれらの片方だけを強制させてしまう。そうすることで、パズルは完全に些細なものになる。つまり、真実の答えを簡単に得ることができる。しかしながら、質問に対する正しい答えを決定する前に、嘘をつくか真実を語るかをランダムが決定すると仮定する、そうしたことはパズルや注釈で述べられていない。

神Aに質問する「もし私があなたに「あなたはランダムですか？」とあなたの現在の精神状態に尋ねたら、あなたはjaと言いますか？」。
もしAがjaと答えるなら、Aがランダム。そこでBに質問する「もし私があなたに「あなたは真ですか？」と尋ねたら、あなたはjaと言いますか？」。
Bがjaと答えるなら、Bは真、Cは偽。
Bがdaと答えるなら、Bは偽、Cは真。どちらの場合もパズルは解決される。
もしAがdaと答えるなら、Aは非ランダム。そこでAに質問する「もし私があなたに「あなたは真ですか？」と尋ねたら、あなたはjaと言いますか？」。
Aがjaと答えるなら、Aは真。
Aがdaと答えるなら、Aは偽。
Aに質問する「もし私があなたに「Bは真ですか？」と尋ねたら、あなたはjaと言いますか？」。
Aがjaと答えるなら、Bがランダム。CはAの反対。
Aがdaと答えるなら、Cがランダム。BはAの反対。

ブーロスにより（「コインが表側ならば彼は真実を語り、もし裏ならば嘘を語る」と）明確化されたオリジナル問題を解決する過程において、意図的で無記述な仮定に頼らずとも、質問にさらなる変更を加えることによって、真実の答えを簡潔に得ることができる。

「もし私があなたにQを尋ねたら、そして仮にあなたがこの質問に答えているように正直にあなたが答えていたとすれば、あなたはjaと言うでしょうか？」

ここで唯一の仮定は、質問に答えている際にランダムが正直に答えている（「真実を語る」）かまたは偽って答えている（「嘘を語る」）かであり、これは明白にブーロスの注釈の一部である。修正なしのオリジナル問題（ブーロスの注釈付き）は、このように、最も洗練された分かりやすい見た目の解決法を有する「真に最難関の論理パズル」だと見なされている。

ラベーン達（2008）は、ランダムが実際のランダムになるように、ブーロスのオリジナルパズルを改正するよう提案している。その修正はブーロスの第3の明確な注釈を以下のものに置き換えることである。

ランダムがjaかdaを言うかどうかは、彼の頭脳に隠されたコイン弾きに応じて考えられるべきである。もしコインが表なら、彼はjaと言い、裏だったら彼はdaと言う。

この修正があると、パズルの解決には解決法項目の冒頭で与えられたものよりもさらに慎重な神への審問が必要になる。

 返答不能な質問と爆発する神の頭 
「真に最難関の論理パズルの簡単な解決法」の論文で、ラベーン達はパズルの改作を提案している。パラドックスに直面した神は、jaもdaもどちらも言わずに、一切答えなくなってしまう。例えば、「あなたはこの質問に、あなたの言葉でノーを意味する言葉で答えるつもりですか？ 」という質問が真実になると、彼は真実を答えることができない。（この論文では、頭が爆発してしまうと表現している。「...彼らは絶対間違えない神です！でも彼らは一つ手段を持っている。頭が爆発する」）。この「爆発頭」が許される場合には、3つではなく2つの質問でパズル（修正済みとオリジナル）を解決する可能性が出てくる。このパズルに対する2質問解決法の裏付けとして、著者は2つの質問だけで同様の簡単なパズルを解決する。

3つの神A、B、Cはこう呼ばれている、順不同で ゼファー、エウロス、アイオロスである。神々は常に真実を話す。あなたの任務は、イエス・ノー質問をしてA、B、Cの正体を決めること。それぞれの質問は正しく1つの神に置く必要がある。神々は人間の言葉を理解し、人間の言葉で答える。

このパズルは3つの質問で自明に解決されることに着目しなさい。さらに、2質問でパズルを解くための、次の補題は証明済みである。

嘘つき気質の補題。もし我々がAに尋ねるとする「こんな場合{[(あなたがこの質問に「ノー」と答えるつもり）かつ（Bはゼファーである)] または（Bはエウロスである)}はありますか？」、に対して「イエス」の返答はBがエウロスであり、「ノー」の返答はBがアイオロスであることを示し、頭が爆発だとBがゼファーであることを示す。したがって、1つの質問でBの正体を決められる。

この補題を使うと、2つの質問でパズルを解くことが簡単になる。ラベーン達（2008）は、きっかり2つの質問で元のパズルを解くために類似の手法（嘘つき気質のパラドックス）を使う。ウスキアノ（2010）は、修正済みパズルに対して2質問での解決法を提示するためにこれらの技法を使っている 
Rabern, Brian and Rabern, Landon. "In defense of the two question solution to the hardest logic puzzle ever". dropbox.com。オリジナルと修正済みパズルの両方に対する2質問の解決法は、一部の神が特定の質問に答えることができないという事実を利用している。真か偽のどちらも、次の質問に対する答えを提供することはできない。

あなたは「キルギスタンにドゥシャンベはあるか？」という質問にランダム（が答えるであろう内容）と同じに答えてくれますか？

修正済みランダムは本当に無作為で答えるので、真か偽のどちらも、ドゥシャンベがキルギスタンにあるかとの質問に、ランダムがdaまたはjaで答えるかどうかを予測できない。この知りえぬ事を与えられると、彼らは真実や嘘が語れなくなってしまう。したがって、彼らは沈黙する。しかしながら、無作為に無意味なことを口走るランダムは、daまたはjaのいずれかを口走っても問題ない。ウスキアノ（2010）は修正済みパズルに対する2質問の解決法を提示するために、この非対称性を流用している。しかし、神様は「ランダムの脳のコイン弾き以前であっても、ランダムの答えを予測するための謎めいた（いわゆる神託）能力」を有するとの仮定もあるだろう。この場合、2質問の解決法は、ラベーン達（2008）に採用されたスタイルの自己参照質問を使用することによって引き続き得ることができる。

この質問にdaで返答するかどうか、という質問にあなたはjaで答えますか？
て
ここでもまた、真か偽のどちらも、真実の証人と嘘つきの約束事をそれぞれ考えると、この質問に答えることができない。彼らは、自分が与えると約束された返答がdaで、これが彼らにできない場合にだけ、jaと答えるよう強制されている。前と同じように、彼らは頭爆発を経験するだろう。対照的に、ランダムは、無分別にたわごとを吐き出して、無作為にjaまたはdaと答えるだろう。ウスキアノ（2010）もまた、修正済みパズルに対する2質問の解決法を提示するために、この非対称性を利用している 。しかしながら、ウスキアノ独自のパズル修正（ランダムが「ja」「da」いずれかを答えるか、または沈黙することにより、この非対称性を解消するというもの）では、3つよりも少ない質問で解決することができなくなっている。

 脚注 

 注釈 

 出典 

 関連項目 
論理パズル
論理演算
デイヴィド・ルイス#可能世界に関する理論（反事実的条件法）

 外部リンク 
Richard Webb. Three gods, three questions: The Hardest Logic Puzzle Ever. (New Scientist, Volume 216, Issues 2896-2897, 22-29 December 2012, Pages 50-52.)
Tom Ellis. Even harder than the hardest logic puzzle ever.
 Jamie Condliffe. The Hardest Logic Puzzle Ever (and How to Solve It).
The Hardest Logic Puzzle Ever (Googlesites page)

Category:数学パズル
Category:論理パズル