Even harder than The Hardest Logic Puzzle Ever

by Tom Ellis

Introduction

George Boolos coined the title The Hardest Logic Puzzle Ever for a puzzle that Wikipedia gives in this form:

Three gods A, B, and C are called, in some 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', in some order. You do not know which word means which.

I have some comments on that definition:

• Rabern and Rabern and Roberts have presented simple solutions to the puzzle (detailed at Wikipedia).

• Rabern and Rabern note that the problem is harder if Random's answers are random, rather than his choice as to whether he should tell the truth or lie (noted at Wikipedia).

• We should suppose that the gods may take an arbitrarily long time to answer questions. This precludes us from asking questions which at least one of the gods cannot answer: if we were to ask it to him, we'd never know if he couldn't answer or if he just hadn't answered yet (cf. recursive enumerability). In this way we avoid the possibility of Rabern and Rabern's "exploding head" answers.

• The gods speak one of two languages from the set L ={ "Daisyesjaisno", "Jaisyesdaisno" }. It's not clear from the Wikipedia article which of the following is to be assumed:

  • There exists a language l in L such that for all gods g, g speaks l (the gods speak the same language)
  • For all gods g, there exists a language l in L such that g speaks l (the gods speak possibly different languages)

Clearly the former leads to (on the face of it) an easier problem, and I suspect that's what the definition intended.

A logic puzzle harder than the hardest ever

Now I wish to extend the puzzle and make it even harder! Then I'll demonstrate how to solve it.

• Suppose there are 2N+1 gods. Each is one of the following three types:
  • A truth teller: they always answer questions truthfully
  • A liar: they always answer questions falsely
  • A randomer: the answer they give to any question is entirely arbitrary

• You don't know how many of each type there are, except that there are no more than N randomers.

• Each god speaks one of the two languages in L, but they might not all share the same language.

• There is a fork in the road. One path leads to the castle. Your task is to find the way to the castle in 2N questions.

(The "castle" question is arbitrary. It's just a question you don't originally know the answer to.)

How can we solve this puzzle?

If you'd like to know how to solve this puzzle, you will find the answer on a separate page.

References

• Wikipedia: The Hardest Logic Puzzle Ever
• George Boolos. The hardest logic puzzle ever. The Harvard Review of Philosophy, 6:62?65, 1996.
• T.S. Roberts. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609?612(4), December 2001.
• Brian Rabern and Landon Rabern. A simple solution to the hardest logic puzzle ever. Analysis 68 (298), 105?112, April 2008.

Thanks

Thanks to Jon Pretty and Richard Smith without whose input I would never have written this article. Thanks to Brian Rabern for his comments on use-mention.