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
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?”

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

### This new data poisoning tool lets artists fight back against generative AI

The tool, called Nightshade, messes up training data in ways that could cause serious damage to image-generating AI models.

### Rogue superintelligence and merging with machines: Inside the mind of OpenAI’s chief scientist

An exclusive conversation with Ilya Sutskever on his fears for the future of AI and why they’ve made him change the focus of his life’s work.

### Unpacking the hype around OpenAI’s rumored new Q* model

If OpenAI's new model can solve grade-school math, it could pave the way for more powerful systems.

### Generative AI deployment: Strategies for smooth scaling

Our global poll examines key decision points for putting AI to use in the enterprise.

### Stay connected

Illustration by Rose Wong

## Get the latest updates fromMIT Technology Review

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

Thank you for submitting your email!