快猫短视频

NEED something to mull other than wine as you atrophy there in the armchair? Then set your grey cells humming with this puzzle.

鈥淭hree 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 鈥榶es鈥� and 鈥榥o鈥� are 鈥榙a鈥� and 鈥榡a鈥�, in some order. You do not know which word means which.鈥�

Welcome to the 鈥淗ardest Logic Puzzle Ever鈥�. If you should happen upon three questions that will unmask the gods, don鈥檛 stop there. Your next task: make the puzzle even harder.

This is a parlour game played by logicians since the Hardest Logic Puzzle Ever was first so named 鈥� and solved 鈥� by US logician George Boolos shortly before his death in 1996. Find a solution, and you understand a little more about how to extract truth in a world where imperfect information abounds 鈥� and perhaps, by the by, about the nature of logic itself.

Boolos always had an individual take on the world. He once delivered a public lecture explaining 鈥榮 second incompleteness theorem, a seminal result in mathematical logic, , and was wont to pace the corridors of the Massachusetts Institute of Technology solving problems with invisible chalk on an invisible blackboard he always carried with him. In formulating the Hardest Logic Puzzle Ever, he was building on a series of mind-benders made popular by US mathematician . In these puzzles, you are marooned on an island among knights, who always speak the truth, and knaves, who do nothing but lie. You generally have one question to extract some vital piece of information from them (see diagram).

鈥淕eorge Boolos was wont to pace the corridors solving problems with invisible chalk on an invisible blackboard鈥�

Boolos鈥檚 genius was to compact into one puzzle so many stumbling blocks that only a fiendishly complex series of questions can lead to the solution. 鈥淲hat makes it hard is the combination: liars and truth-tellers, language ignorance and finally a random element,鈥� says , a philosopher at the University of Illinois at Urbana-Champaign. To reproduce Boolos鈥檚 full answer, which he in The Harvard Review of Philosophy, would be to spoil the fun. For those needing a head start: his first question, addressed to god A, is, 鈥淒oes 鈥榙a鈥� mean 鈥榶es鈥� if and only if you are True if and only if god B is Random鈥�. Now get out those invisible chalkboards.

Boolos鈥檚 intention in formulating the puzzle was not entirely frivolous. His solution stood or fell on extensive use of one of three classical axioms of logic attributed to Aristotle. Known as the law of excluded middle, it states that a logical proposition must be either true or false; there is no third way.

But is the law of the excluded middle itself true (and if not, is it false)? Consider, for example, the statement, 鈥淭he present King of America has a beard鈥�. Is it necessarily false by virtue of there being no King of America, or does it lie in some grey zone between truth and falsehood? With his solution to the Hardest Puzzle, Boolos aimed to show how difficult it becomes to solve logical problems if one allowed such a middle way.

His solution was not to everyone鈥檚 taste. As Tim Roberts of Central Queensland University in Bundaberg, Australia, observed tartly in 2001, the obfuscating 鈥渋f and only if鈥� statements with which Boolos laced his solution were 鈥渢he sort of thing that makes most laymen despair of logicians鈥�. Producing a solution that did away with them, Roberts concluded that the Hardest Puzzle was not so hard after all, and went on to suggest two : make two gods Random, and the third either True or False; or one god Random and the other two indeterminately either True or False.

The floodgates really opened in 2008, though, when Brian Rabern and his brother discovered a more fundamental flaw in Boolos鈥檚 original puzzle. It lay in his clarification of how Random generates his answers: like flipping a coin, Boolos specified, where heads makes him speak the truth and tails forces him to lie. In that case, said the Rabern brothers, just ask the question, 鈥淎re you going to answer this question with a lie?鈥�. True and False can only answer this question with the word meaning 鈥渘o鈥�. If Random鈥檚 coin shows heads, meanwhile, he must speak truly and also say the word for 鈥渘o鈥�. Equally, if it shows tails, he must lie 鈥� again answering in the negative. So whoever you are speaking to, you now know how to say 鈥渘o鈥� in the gods鈥� language.

Head-exploders

This allows the problem to be solved in three . That isn鈥檛 all: similarly self-referential questions can also throw True and False into utter confusion. For example, ask them, 鈥淎re you going to answer 鈥榡a鈥� to this question?鈥�. If 鈥渏a鈥� means 鈥渘o鈥� True cannot say the truth, and if it means 鈥測es鈥� False cannot say a lie, so one or other of them will be left lost for words. 鈥淲e called them head-exploding questions,鈥� says Brian Rabern.

Such undefined statements are the bane of unwary computer programmers, producing a program that is paralysed by indecision. But the Rabern brothers showed how using these statements judiciously unmasked True and False quicker and helped to solve the puzzle in just two questions. Even when Random鈥檚 behaviour was tweaked to make him answer truly randomly, the puzzle was easily solvable in three steps.

And so it went on. While the validity of head-exploding questions remains questioned (see 鈥�Explosive logic鈥�), in 2010 philosopher of the University of Oxford embedded them in more complex logical structures to show that you could also solve the truly random version of the puzzle with just 鈥� and then came up with a harder variant in which Random could randomly decide to say nothing at all. Later that year, of Carnegie Mellon University in Pittsburgh, Pennsylvania, and his colleague Pedro Barahona responded with to Uzquiano鈥檚 problem in three questions. A still harder puzzle could be formulated, they suggested, by replacing Random with Devious, who lies when he can but if he gets confused acts like Random.

At the moment, they have their peers stumped with this version. 鈥淲e have seen some papers come through, but nothing has quite got there,鈥� says Wheeler.

So what more is there to this, beyond logical one-upmanship? Quite a bit. 鈥淚t is not just about logic, it is about information extraction, learning about nature when she is unwilling to give up her secrets,鈥� says Wheeler. Brian Rabern agrees. 鈥淭he god Random makes it a toy model of reasoning with imperfect information, which we must do all the time in normal life,鈥� he says. By clarifying how we do that most efficiently, the puzzle hones our logical arsenal 鈥� an understanding that could help us to program artificial intelligences to reason about the world.

That thought inspired Nikolay Novozhilov, a hobby puzzler based in Singapore, to bind our hands even tighter. Earlier this year, he modified the puzzle鈥檚 set-up so you are given no clues about the gods鈥� language. This means we cannot ask questions such as, 鈥淚f I asked you X, would you answer 鈥榙a鈥�?鈥�. 鈥淭he idea was to find out, if you eliminate all understanding, is it still solvable?鈥� he says.

The , provided whoever is being questioned has developed distinct ways to express basic logical concepts such as true and false. That result feeds into a long-running debate between linguists as to the minimum requirement to build a lexicon of a completely unknown language. Novozhilov playfully suggests one situation in which it might come in useful: that first encounter with the little green men. 鈥淚 am sure that aliens will have the same understanding of logic whatever world they live in,鈥� he says. 鈥淓ven if you don鈥檛 have any information about how someone communicates, this shows there are features you can predict just from a logical understanding of what language is about.鈥�

Perhaps that is an unnecessarily unnerving suggestion with which to justify some fireside puzzle-solving. Wheeler suggests we need not look so far afield for a motivation. 鈥淭here is something aesthetically lovely about a well-made puzzle.鈥�