Boolos' “The Hardest Logic Puzzle Ever” and coinduction (Group, Ring, Language and Related Areas in Computer Science)

Abstract

Boolos (1996) posed the puzzle "The hardest logic puzzle ever", and gave a solution in the style of biconditional questions. We first introduce a simple formalization of the puzzle consisting of questions, answerers, and answers in terms of propositional logic, and show its adequacy by the truth values (0, 1) semantics. We here pose a general form of the puzzle as an extension of Roberts (2001), and provide solutions to the instances. Our analysis reveals an essential condition for solvability of the puzzle in terms of the number of Random.