The Hardest Logic Puzzle Ever

Last updated

The Hardest Logic Puzzle Ever is a logic puzzle so called by American philosopher and logician George Boolos and published in The Harvard Review of Philosophy in 1996. [1] [2] Boolos' article includes multiple ways of solving the problem. A translation in Italian was published earlier in the newspaper La Repubblica , under the title L'indovinello più difficile del mondo.

Contents

It is stated as follows:

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes–no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, [3] in some order. You do not know which word means which.

Boolos provides the following clarifications: [1] a single god may be asked more than one question, questions are permitted to depend on the answers to earlier questions, and the nature of Random's response should be thought of as depending on the flip of a fair coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely. [4]

History

Boolos credits the logician Raymond Smullyan as the originator of the puzzle and John McCarthy with adding the difficulty of not knowing what da and ja mean. Related puzzles can be found throughout Smullyan's writings. For example, in What is the Name of This Book? , [5] he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth). He explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes–no question, they reply Bal or Ja—one of which means yes and the other no. The trouble is that we do not know which of Bal or Da means yes and which means no." There are other related puzzles in The Riddle of Scheherazade. [6] [7]

The puzzle is based on Knights and Knaves puzzles. One setting for this puzzle is a fictional island inhabited only by knights and knaves, where knights always tell the truth and knaves always lie. A visitor to the island must ask a number of yes/no questions in order to discover what he needs to know (the specifics of which vary between different versions of the puzzle). One version of these puzzles was popularized by a scene in the 1986 fantasy film Labyrinth . There are two doors, each with one guard. One guard always lies and the other always answers truthfully. One door leads to the castle and the other leads to 'certain death'. The puzzle is to find out which door leads to the castle by asking one of the guards one question. In the movie, the protagonist does this by asking "Would he [the other guard] tell me that this door leads to the castle?"

The solution

Boolos provided his solution in the same article in which he introduced the puzzle. Boolos states that the "first move is to find a god that you can be certain is not Random, and hence is either True or False". [1] There are many different questions that will achieve this result. One strategy is to use complicated logical connectives in your questions (either biconditionals or some equivalent construction).

Boolos' question was to ask A:

Does da mean yes if and only if you are True, if and only if B is Random? [1]

Equivalently:

Are an odd number of the following statements true: da means yes, you are True, B is Random?

It was observed by Roberts (2001) and independently by Rabern and Rabern (2008) that the puzzle's solution can be simplified by using certain counterfactuals. [6] [8] The key to this solution is that, for any yes/no question Q, asking either True or False the question

If I asked you Q, would you say ja?

results in the answer ja if the truthful answer to Q is yes, and the answer da if the truthful answer to Q is no (Rabern and Rabern (2008) call this result the embedded question lemma). The reason this works can be seen by studying the logical form of the expected answer to the question. This logical form (Boolean expression ) is developed below ('Q' is true if the answer to Q is 'yes', 'God' is true if the god to whom the question is asked is acting as a truth-teller and 'Ja' is true if the meaning of Ja is 'yes'):

  1. How a god would choose to answer Q is given by the negation of the exclusive disjunction between Q and God (if the answer to Q and the nature of the god are opposite, the answer given by the god is bound to be 'no', while if they are the same, it is bound to be 'yes'):
    • ¬ ( Q ⊕ God)
  2. Whether the answer given by the god would be Ja or not is given again by the negation of the exclusive disjunction between the previous result and Ja
    • ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja )
  3. The result of step two gives the truthful answer to the question: 'If I ask you Q, would you say ja'? What would be the answer the God will give can be ascertained by using reasoning similar to that used in step 1
    • ¬ ( ( ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) ) ⊕ God )
  4. Finally, to find out if this answer will be Ja or Da, (yet another) negation of the exclusive disjunction of Ja with the result of step 3 will be required
    • ¬ ( ( ¬ ( ( ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) ) ⊕ God ) ) ⊕ Ja )

This final expression evaluates to true if the answer is Ja, and false otherwise. The eight cases are worked out below (1 represents true, and 0 false):

Q

True if answer to

Q is 'yes'

God

True if god behaves

as truth-teller

Ja

True if meaning of

Ja is 'yes'

Step 1

(God's answer to Q)

Step 2

(Is it Ja?)

Step 3

(God's answer to counterfactual)

Step 4

(Is it Ja?)

0001010
0011100
0100110
0110000
1000101
1010011
1101001
1111111

Comparing the first and last columns makes it plain to see that the answer is Ja only when the answer to the question is 'yes'. The same results apply if the question asked were instead: 'If I asked you Q, would you say Da'? because the evaluation of the counterfactual does not depend superficially on meanings of Ja and Da. Each of the eight cases are equivalently reasoned out below in words:

  1. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is ja, which means yes.
  2. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is da, which means no.
  3. False is asked and responds with ja. Since he is lying, it follows that if you asked him Q, he would instead answer da. He would be lying, so the truthful answer to Q is ja, which means yes.
  4. False is asked and responds with da. Since he is lying, it follows that if you asked him Q, he would in fact answer ja. He would be lying, so the truthful answer to Q is da, which means no.
  1. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is da, which means yes.
  2. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is ja, which means no.
  3. False is asked and responds with ja. Since he is lying, it follows that if you asked him Q, he would in fact answer ja. He would be lying, so the truthful answer to Q is da, which means yes.
  4. False is asked and responds with da. Since he is lying, it follows that if you asked him Q, he would instead answer da. He would be lying, so the truthful answer to Q is ja, which means no.

Regardless of whether the asked god is lying or not and regardless of which word means yes and which no, you can determine if the truthful answer to Q is yes or no.

The solution below constructs its three questions using the lemma described above. [6]

Q1: Ask god B, "If I asked you 'Is A Random?', would you say ja?". If B answers ja, either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers da, either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, you know the identity of a god who is not Random.
Q2: Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: "If I asked you 'Are you False?', would you say ja?". Since he is not Random, an answer of da indicates that he is True and an answer of ja indicates that he is False.
Q3: Ask the same god the question: "If I asked you 'Is B Random?', would you say ja?". If the answer is ja, B is Random; if the answer is da, the god you have not yet spoken to is Random. The remaining god can be identified by elimination.
Case12345678910111213141516
ATrueTrueFalseRandomFalseRandomTrueTrueFalseRandomFalseRandom
BFalseRandomTrueTrueRandomFalseFalseRandomTrueTrueRandomFalse
CRandomFalseRandomFalseTrueTrueRandomFalseRandomFalseTrueTrue
DaYesYesYesYesYesYesNoNoNoNoNoNo
JaNoNoNoNoNoNoYesYesYesYesYesYes
Is A indeed Random?NoNoNoYesNoYesNoNoNoYesNoYes
How would B answer "Is A Random?"EnglishYesEitherNoYesEitherNoYesEitherNoYesEitherNo
Their languageDaEitherJaDaEitherJaJaEitherDaJaEitherDa
B's response to Question 1—"If I asked you 'Is A Random', would you say ja?"EnglishYesEitherYesNoEitherNoNoEitherNoYesEitherYes
Their languageDaEitherDaJaEitherJaDaEitherDaJaEitherJa
DaJaDaJaDaJaDaJa
Thus __ (hereafter called X) is not Random.AACACACCAACACACC
Is X indeed False?NoNoYesYesYesYesNoNoNoNoYesYesYesYesNoNo
How would X answer "Are you False?"EnglishNoNoNoNoNoNoNoNoNoNoNoNoNoNoNoNo
Their languageJaJaJaJaJaJaJaJaDaDaDaDaDaDaDaDa
X's response to Question 2—"If I asked you 'Are you False?', would you say ja?"EnglishYesYesNoNoNoNoYesYesNoNoYesYesYesYesNoNo
Their languageDaDaJaJaJaJaDaDaDaDaJaJaJaJaDaDa
Thus X is __. TrueTrueFalseFalseFalseFalseTrueTrueTrueTrueFalseFalseFalseFalseTrueTrue
Is B indeed Random?NoYesNoNoYesNoNoYesNoNoYesNo
How would X answer "Is B Random?"EnglishNoYesNoYesYesNoYesNoNoYesNoYesYesNoYesNo
Their languageJaDaJaDaDaJaDaJaDaJaDaJaJaDaJaDa
X's response to Question 3—"If I asked you 'Is B Random?', would you say ja?"EnglishYesNoNoYesYesNoNoYesNoYesYesNoNoYesYesNo
Their languageDaJaJaDaDaJaJaDaDaJaJaDaDaJaJaDa
Thus __ is Random.CBBCABBACBBCABBA
Thus by elimination, (Letter) is (Name).LetterBCABBCABBCABBCAB
NameFalseFalseTrueTrueTrueTrueFalseFalseFalseFalseTrueTrueTrueTrueFalseFalse

Random's behavior

Boolos' third clarifying remark explains Random's behavior as follows: [6]

Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

This does not state if the coin flip is for each question, or each "session", that is the entire series of questions. If interpreted as being a single random selection which lasts for the duration of the session, Rabern and Rabern show that useful answers can be extracted even from Random; [6] this is because the counterfactual had been designed such that regardless of whether the answerer (in this case Random) was as a truth-teller or a false-teller, the truthful answer to Q would be clear.

Another possible interpretation of Random's behaviour when faced with the counterfactual is that he answers the question in its totality after flipping the coin in his head, but figures out the answer to Q in his previous state of mind, while the question is being asked. Once again, this makes asking Random the counterfactual useless. If this is the case, a small change to the question above yields a question which will always elicit a meaningful answer from Random. The change is as follows:

If I asked you Q in your current mental state, would you say ja? [6]

This effectively extracts the truth-teller and liar personalities from Random and forces him to be only one of them. By doing so the puzzle becomes completely trivial, that is, truthful answers can be easily obtained. However, it assumes that Random has decided to lie or tell the truth prior to determining the correct answer to the question – something not stated by the puzzle or the clarifying remark.

Ask god A, "If I asked you 'Are you Random?' in your current mental state, would you say ja?"
  1. If A answers ja, A is Random: Ask god B, "If I asked you 'Are you True?', would you say ja?"
    • If B answers ja, B is True and C is False.
    • If B answers da, B is False and C is True. In both cases, the puzzle is solved.
  2. If A answers da, A is not Random: Ask god A, "If I asked you 'Are you True?', would you say ja?"
    • If A answers ja, A is True.
    • If A answers da, A is False.
  3. Ask god A, "If I asked you 'Is B Random?', would you say ja?"
    • If A answers ja, B is Random, and C is the opposite of A.
    • If A answers da, C is Random, and B is the opposite of A.

One can elegantly obtain truthful answers in the course of solving the original problem as clarified by Boolos ("if the coin comes down heads, he speaks truly; if tails, falsely") without relying on any purportedly unstated assumptions, by making a further change to the question:

If I asked you Q, and if you were answering as truthfully as you are answering this question, would you say ja?

Here, the only assumption is that Random, in answering the question, is either answering truthfully ("speaks truthfully") OR is answering falsely ("speaks falsely") which are explicitly part of the clarifications of Boolos. The original unmodified problem (with Boolos' clarifications) in this way can be seen to be the "Hardest Logical Puzzle Ever" with the most elegant and uncomplicated looking solution.

Rabern and Rabern (2008) suggest making an amendment to Boolos' original puzzle so that Random is actually random. The modification is to replace Boolos' third clarifying remark with the following: [6]

Whether Random says ja or da should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he says ja; if tails, he says da.

With this modification, the puzzle's solution demands the more careful god-interrogation given at the top of The Solution section.

Unanswerable questions and exploding god-heads

In A simple solution to the hardest logic puzzle ever, [6] B. Rabern and L. Rabern offer a variant of the puzzle: a god, confronted with a paradox, will say neither ja nor da and instead not answer at all. For example, if the question "Are you going to answer this question with the word that means no in your language?" is put to True, he cannot answer truthfully. (The paper represents this as his head exploding, "...they are infallible gods! They have but one recourse – their heads explode.") Allowing the "exploding head" case gives yet another solution of the puzzle and introduces the possibility of solving the puzzle (modified and original) in just two questions rather than three. In support of a two-question solution to the puzzle, the authors solve a similar simpler puzzle using just two questions.

Three gods A, B, and C are called, in some order, Zephyr, Eurus, and Aeolus. The gods always speak truly. Your task is to determine the identities of A, B, and C by asking yes–no questions; each question must be put to exactly one god. The gods understand English and will answer in English.

Note that this puzzle is trivially solved with three questions. Furthermore, to solve the puzzle in two questions, the following lemma is proved.

Tempered Liar Lemma. 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)}?", a response of 'yes' indicates that B is Eurus, a response of 'no' indicates that B is Aeolus, and an exploding head indicates that B is Zephyr. Hence we can determine the identity of B in one question.

Using this lemma it is simple to solve the puzzle in two questions. Rabern and Rabern (2008) use a similar trick (tempering the liar's paradox) to solve the original puzzle in just two questions. Uzquiano (2010) uses these techniques to provide a two question solution to the amended puzzle. [9] [10] Two question solutions to both the original and amended puzzle take advantage of the fact that some gods have an inability to answer certain questions. Neither True nor False can provide an answer to the following question.

Would you answer the same as Random would to the question 'Is Dushanbe in Kirghizia?'?

Since the amended Random answers in a truly random manner, neither True nor False can predict whether Random would answer ja or da to the question of whether Dushanbe is in Kirghizia. Given this ignorance they will be unable to tell the truth or lie – they will therefore remain silent. Random, however, who spouts random nonsense, will have no problem spouting off either ja or da. Uzquiano (2010) exploits this asymmetry to provide a two question solution to the modified puzzle. Yet, one might assume that the gods have an "oracular ability to predict Random's answers even before the coin flip in Random’s brain?" [9] In this case, a two question solution is still available by using self-referential questions of the style employed in Rabern and Rabern (2008).

Would you answer ja to the question of whether you would answer da to this question?

Here again neither True nor False are able to answer this question given their commitments of truth-telling and lying, respectively. They are forced to answer ja just in case the answer they are committed to give is da and this they cannot do. Just as before they will suffer a head explosion. In contrast, Random will mindlessly spout his nonsense and randomly answer ja or da. Uzquiano (2010) also uses this asymmetry to provide a two question solution to the modified puzzle. [9] [10] However, Uzquiano's own modification to the puzzle, which eliminates this asymmetry by allowing Random to either answer "ja", "da", or remain silent, cannot be solved in fewer than three questions. [11]

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In philosophy and logic, the classical liar paradox or liar's paradox or antinomy of the liar is the statement of a liar that they are lying: for instance, declaring that "I am lying". If the liar is indeed lying, then the liar is telling the truth, which means the liar just lied. In "this sentence is a lie" the paradox is strengthened in order to make it amenable to more rigorous logical analysis. It is still generally called the "liar paradox" although abstraction is made precisely from the liar making the statement. Trying to assign to this statement, the strengthened liar, a classical binary truth value leads to a contradiction.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.

In classical rhetoric and logic, begging the question or assuming the conclusion is an informal fallacy that occurs when an argument's premises assume the truth of the conclusion. Historically, begging the question refers to a fault in a dialectical argument in which the speaker assumes some premise that has not been demonstrated to be true. In modern usage, it has come to refer to an argument in which the premises assume the conclusion without supporting it. This makes it an example of circular reasoning.

<span class="mw-page-title-main">Raymond Smullyan</span> American mathematician and logician

Raymond Merrill Smullyan was an American mathematician, magician, concert pianist, logician, Taoist, and philosopher.

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.

Situation puzzles are often referred to as minute mysteries, lateral thinking puzzles or "yes/no" puzzles.

Knights and Knaves is a type of logic puzzle where some characters can only answer questions truthfully, and others only falsely. The name was coined by Raymond Smullyan in his 1978 work What Is the Name of This Book?

Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word infer means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in Europe dates at least to Aristotle. Deduction is inference deriving logical conclusions from premises known or assumed to be true, with the laws of valid inference being studied in logic. Induction is inference from particular evidence to a universal conclusion. A third type of inference is sometimes distinguished, notably by Charles Sanders Peirce, contradistinguishing abduction from induction.

<span class="mw-page-title-main">George Boolos</span> American philosopher and mathematical logician

George Stephen Boolos was an American philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.

Randomised response is a research method used in structured survey interview. It was first proposed by S. L. Warner in 1965 and later modified by B. G. Greenberg and coauthors in 1969. It allows respondents to respond to sensitive issues while maintaining confidentiality. Chance decides, unknown to the interviewer, whether the question is to be answered truthfully, or "yes", regardless of the truth.

<i>The Foundations of Arithmetic</i> Book by Gottlob Frege

The Foundations of Arithmetic is a book by Gottlob Frege, published in 1884, which investigates the philosophical foundations of arithmetic. Frege refutes other idealist and materialist theories of number and develops his own platonist theory of numbers. The Grundlagen also helped to motivate Frege's later works in logicism.

<i>The Moment of Truth</i> (American game show) American game show

The Moment of Truth is an American game show based on the Colombian Nada más que la verdad format. Contestants answer a series of 21 increasingly personal and embarrassing questions to receive cash prizes. The show was hosted by Mark L. Walberg and ran on the Fox network from January 23, to August 28, 2008.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.

Yes and no, or similar word pairs, are expressions of the affirmative and the negative, respectively, in several languages, including English. Some languages make a distinction between answers to affirmative versus negative questions and may have three-form or four-form systems. English originally used a four-form system up to and including Early Middle English. Modern English uses a two-form system consisting of yes and no. It exists in many facets of communication, such as: eye blink communication, head movements, Morse code, and sign language. Some languages, such as Latin, do not have yes-no word systems.

<span class="mw-page-title-main">Pinocchio paradox</span> Variant of the liar paradox

The Pinocchio paradox arises when Pinocchio says "My nose grows now" and is a version of the liar paradox. The liar paradox is defined in philosophy and logic as the statement "This sentence is false." Any attempts to assign a classical binary truth value to this statement lead to a contradiction, or paradox. This occurs because if the statement "This sentence is false" is true, then it is false; this would mean that it is technically true, but also that it is false, and so on without end. Although the Pinocchio paradox belongs to the liar paradox tradition, it is a special case because it has no semantic predicates, as for example "My sentence is false" does.

<span class="mw-page-title-main">Buridan's bridge</span> Logical paradox

Buridan's Bridge is described by Jean Buridan, one of the most famous and influential philosophers of the Late Middle Ages, in his book Sophismata. It is a self-referential paradox that involves a proposition pronounced about an event that might or might not happen in the future.

Coercive logic is a concept popularised by mathematician Raymond Smullyan, by which a person who has agreed to answer a question truthfully is forced to perform an undesired action, where not doing so would mean breaking their agreement. Smullyan presents the concept as a question:

Suppose I offer you a million dollars to answer a yes/no question truthfully, would you accept the offer? If so, you shouldn't, for I would then ask: Will you either answer no to this question or pay me two million dollars? The only way you can answer truthfully is by answering yes and then paying me two million dollars.

References

  1. 1 2 3 4 Boolos, George (1996). "The hardest logic puzzle ever" (PDF). The Harvard Review of Philosophy . 6: 62–65. doi:10.5840/harvardreview1996615. Archived from the original (PDF) on 30 January 2023.
  2. Kazmi, Kumail (April 14, 2021). "The Hardest Logic Puzzle Ever? (with Answer)". Puzzleness - Encyclopedia of Puzzles. Puzzleness. Retrieved April 14, 2021.
  3. Da means yes in Russian, ja means yes in German.
  4. Note that the Random god in Boolos' puzzle is a god who acts randomly as either a truth-teller or a liar. This is different from a god who answers 'yes' or 'no' randomly. One usual trick in solving many logic puzzles is to design a (perhaps composite) question that forces both a truth-teller and a liar to answer 'yes'. For such a question, a person who randomly chooses to be a truth-teller or a liar is still forced to answer 'yes', but a person who answers randomly may answer 'yes' or 'no'.
  5. Smullyan, Raymond (1978). What is the Name of This Book?. Englewood Cliffs, New Jersey: Prentice Hall. pp. 149–156.
  6. 1 2 3 4 5 6 7 8 Rabern, B.; Rabern, L. (2008). "A simple solution to the hardest logic puzzle ever" (PDF). Analysis. 68 (298): 105. doi:10.1111/j.1467-8284.2007.00723.x.
  7. Smullyan, Raymond (1997). The Riddle of Scheherazade. New York: A. A. Knopf, Inc.
  8. Roberts, T. S. (2001). "Some Thoughts about the Hardest Logic Puzzle Ever". Journal of Philosophical Logic. 30 (6): 609–612. doi:10.1023/a:1013344220298. S2CID   207556092.
  9. 1 2 3 Uzquiano, G. (2009). "How to solve the hardest logic puzzle ever in two questions". Analysis. 70: 39–44. doi:10.1093/analys/anp140.
  10. 1 2 Rabern, Brian and Rabern, Landon. "In defense of the two question solution to the hardest logic puzzle ever". dropbox.com
  11. Wheeler, G.; Barahona, P. (2011). "Why the Hardest Logic Puzzle Ever Cannot Be Solved in Less than Three Questions" (PDF). Journal of Philosophical Logic. 41 (2): 493. doi:10.1007/s10992-011-9181-7. S2CID   33036814.