Skip to Content
Artificial intelligence

‘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

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.

Deep Dive

Artificial intelligence

Why Meta’s latest large language model survived only three days online

Galactica was supposed to help scientists. Instead, it mindlessly spat out biased and incorrect nonsense.

DeepMind’s game-playing AI has beaten a 50-year-old record in computer science

The new version of AlphaZero discovered a faster way to do matrix multiplication, a core problem in computing that affects thousands of everyday computer tasks.

A bot that watched 70,000 hours of Minecraft could unlock AI’s next big thing

Online videos are a vast and untapped source of training data—and OpenAI says it has a new way to use it.

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.