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.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

Want more award-winning journalism? Subscribe to Insider Basic.
  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning print magazine, unlimited online access plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

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