真に最難関の論理パズル

出典: フリー百科事典『ウィキペディア(Wikipedia)』

真に最難関の論理パズル(まさにさいなんかんのろんりパズル、The Hardest Logic Puzzle Ever) [注釈 1] とは、アメリカの哲学者で論理学者のジョージ・ブーロス英語版がそう呼んでいた、1996年に「The Harvard Review of Philosophy」で掲載された論理パズルである[1] 。問題を解決する複数の方法がブーロスの論説にあり、イタリア語翻訳が「世界で最も危険なパズル」というタイトルで、新聞ラ・レプッブリカに掲載された。

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

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

ブーロスは以下の注釈も付けている[2]。単一の神様に複数の質問をしてもよい。前回質問の答えに依存した質問をしてもかまわない。ランダムの性質は彼の脳内に隠されている公正なコインを弾いた裏表に準じており、それが表側なら真実を語り、裏ならば嘘を語る[注釈 3]

歴史[編集]

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

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

解決法[編集]

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

ブーローズの質問はAに尋ねるもので[2]

もしBがランダムである場合で、もしあなたが真である場合なら、daはイエスという意味ですか?


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

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

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

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

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つのケースそれぞれは、下の言葉で等しく推論される[注釈 4]

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

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

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

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 No
Jaの意味 No No No No No No Yes Yes Yes Yes Yes Yes
Aは実際にランダムか? 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 C
Xは実際に偽か? 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つ目の注釈は、ランダムの行動を以下のように説明している[4]

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

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

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

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

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

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


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

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

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


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

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

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

返答不能な質問と爆発する神の頭[編集]

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

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

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

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

この補題を使うと、2つの質問でパズルを解くことが簡単になる。ラベーン達(2008)は、きっかり2つの質問で元のパズルを解くために類似の手法(嘘つき気質のパラドックス)を使う。ウスキアノ(2010)は、修正済みパズルに対して2質問での解決法を提示するためにこれらの技法を使っている[7] [8]。オリジナルと修正済みパズルの両方に対する2質問の解決法は、一部の神が特定の質問に答えることができないという事実を利用している。真か偽のどちらも、次の質問に対する答えを提供することはできない。

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

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

この質問にdaで返答するかどうか、という質問にあなたはjaで答えますか?

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

脚注[編集]

注釈[編集]

  1. ^ 最上級+EVERは、最上級の強調表現で「まさしく、かつてない」などと訳される。この論理パズルは神の真、偽などを決めるので、掛詞も込めて「真に(まさに)」との翻訳を付けた。
  2. ^ 答え方が「Yes(はい)」または「No(いいえ)」の二択になるような質問のこと。
  3. ^ ブーロスのパズルにおけるランダム神は、真実の証人か嘘つきのどちらかとして、ランダムに行動する神であることに注意しなければならない。 これは無作為に「yes」または「no」と答える神とは異なる。多くの論理パズルを解決する一般的手口は、真実の証人と嘘つきの両方に「yes」と答えさせる質問(恐らく複合した)を設計することにある。そういった質問に対し、真実の証人か嘘つきかをランダムに選択した者は依然として「yes」と答えざるをえないが、無作為に答える人は「yes」または「no」と答えることがある。
  4. ^ これらは「もし私があなたにQ(任意のイエスノー質問)を尋ねたら、あなたはJaと言うでしょうか?」の質問に対する神の返答に関する解釈8ケース。
  5. ^ 3神の名前の由来はアネモイを参照。本文との関連性は皆無であり、たまたまこれらの名前が使用されたに過ぎない。
  6. ^ 質問文章が不格好に見えるが、英語版en:The Hardest Logic Puzzle Everの原文が、If we ask A "Is it the case that {[(you are going to answer 'no' to this question) AND (B is Zephyr)] OR (B is Eurus)}?"なので、これを忠実に訳したものである。

出典[編集]

  1. ^ George Boolos, 'The Hardest Logic Puzzle Ever'. The Harvard Review of Philosophy, Volume 6 (1996), pp.62-65 https://doi.org/10.5840/harvardreview1996615.
  2. ^ a b c Boolos, George (1996). “The hardest logic puzzle ever”. The Harvard Review of Philosophy 6: 62–65. http://www.hcs.harvard.edu/~hrp/issues/1996/Boolos.pdf. 
  3. ^ Smullyan, Raymond (1978). What is the Name of This Book?. Englewood Cliffs, New Jersey: Prentice Hall. pp. 149–156 
  4. ^ a b c d e f g h 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.
  5. ^ Smullyan, Raymond (1997). The Riddle of Scheherazade. New York: A. A. Knopf, Inc 
  6. ^ Roberts, T. S. (2001). “Some Thoughts about the Hardest Logic Puzzle Ever”. Journal of Philosophical Logic 30 (6): 609. doi:10.1023/a:1013344220298. 
  7. ^ a b c Uzquiano, G. (2009). “How to solve the hardest logic puzzle ever in two questions”. Analysis 70: 39. doi:10.1093/analys/anp140. 
  8. ^ a b Rabern, Brian and Rabern, Landon. "In defense of the two question solution to the hardest logic puzzle ever". dropbox.com
  9. ^ Wheeler, G.; Barahona, P. (2011). “Why the Hardest Logic Puzzle Ever Cannot Be Solved in Less than Three Questions”. Journal of Philosophical Logic 41 (2): 493. doi:10.1007/s10992-011-9181-7. 

関連項目[編集]

外部リンク[編集]