用户工具

站点工具


interview:the-hardest-logic-puzzle-ever

史上最难的逻辑谜题(The Hardest Logic Puzzle Ever)

有三个精灵,一个只说真话,一个只说假话,另一个随机说真话或者假话。你可以向这三个精灵问三个是非题,每次问谁都可以,下一个问题可以根据上一个问题的答案来问。你的任务就是判断他们的身份。不幸的是,他们可以听懂你的话,却用他们的方言—— Da 和 Ja ——来回答。你不知道那个表示对,哪个表示错。那么,你应该问哪三个问题呢?

这个标题党要归功于麻省理工学院的逻辑学家乔治·史蒂芬·布罗斯(George Stephen Boolos)。1996 年,他在《哈佛哲学评论》(The Harvard Review of Philosophy)发表了同名文章,文章中说这个谜题是由美国数学家雷蒙德·斯穆里安(Raymond Smullyan)发明的。

谜题看上去有点绕,其实事情原本没有这么复杂。斯穆里安曾经提出过这个问题的简化版本“骑士与流氓”(Knights and Knaves),里面没有情绪不稳定的第三者,而且他们说的话你也听得懂。

后来有人嫌这个不够难,就加了“你听不懂他们的话”这个条件。这个人就是图灵奖获得者约翰·麦卡锡(John McCarthy)。再后来,题目又多出了一个第三者,这样便算得上是“史上最难的逻辑谜题”了。

这些相关的谜题都可以在斯穆里安的《这本书叫什么名字》(What is the name of this book)和《舍赫拉查德的谜题》(The Riddle of Scheherazade)中看到。

interview/the-hardest-logic-puzzle-ever.txt · 最后更改: 2011/04/25 13:51 (外部编辑)