Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

'The Hardest Logic Puzzle Ever' Made Even Harder

The process of making a famous problem in logic even harder reveals fascinating insights into the relationship between logic and language

  • June 13, 2012

In 1996, the mathematical logician George Boolos (above) published a paper describing “the hardest logic puzzle ever” which he attributed to the logician Raymond Smullyan.

The puzzle has gained much attention.Here it is in all its glory:

“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.” 

Boolos says the first move must be to find a God you can be certain isn’t Random and so must be True or False. 

It turns out there are many ways to do this. Boolos’s solution, which he published in the paper, was to ask the following question: 

“Does da mean yes if and only if you are True if and only if B is Random?”

which is equivalent to asking:

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

A few years later, however, others found that there was a simpler solution based on counterfactual questions like this:

“If I asked you Q, would you say ja?”

where Q is some question such as “Is A Random?”. This is known as an embedded question lemma.

The God must answer ja if the truthful answer to Q is yes and da if the truthful answer to Q is no.
Today, the independent researcher Nikolay Novozhilov has modified Boolos’s original puzzle in a way that makes it harder.

His modification is to remove any knowledge about the Gods’ language other than that they all speak the same language and use the same words for yes and no, rather than synonyms.   He calls this complete language ignorance.

Novozhilov says this puzzle is much harder because it has fewer answers. I won’t spoil the fun by revealing his answer here. The link to the paper is below

What’s interesting abut this puzzle however, is the insights it gives into the logic of language discovery. Given an entirely unknown language–it might involve whistles or smells or vibrations–Novozhilov’s approach shows that there are always ways to extract important knowledge about this language with a few carefully chosen questions.

There’s a caveat, of course: you have to be talking to omniscient Gods who understand English but refuse to speak it. So if you ever find yourself in that situation, make sure to have a copy of Novozhilov’s paper to hand.

Ref: arxiv.org/abs/1206.1926 The Hardest Logic Puzzle Ever Becomes Even Tougher.

Want to go ad free? No ad blockers needed.

Become an Insider
Already an Insider? Log in.
Want more award-winning journalism? Subscribe to Insider Plus.
  • Insider Plus {! insider.prices.plus !}*

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    Print + Digital Magazine (6 bi-monthly issues)

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

    Technology Review PDF magazine archive, including articles, images, and covers dating back to 1899

    10% Discount to MIT Technology Review events and MIT Press

    Ad-free website experience

/3
You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.