Als schwierigstes Rätsel der Welt (wörtlich: aller Zeiten, ) bezeichnete der US-amerikanische Philosoph und Logiker George Boolos ein auf den Mathematiker Raymond Smullyan zurückgehendes Denkspiel. Es stellt eine Herausforderung der formalen Logik dar und hat durch seine Konstruktion weltweite Aufmerksamkeit erlangt.

Das Rätsel handelt von drei Göttern, von denen einer stets die Wahrheit sagt, einer immer lügt und ein weiterer zufällig antwortet, wobei sie ihre eigene Sprache benutzen. Aufgabe ist, die drei Götter mithilfe von nur drei Entscheidungsfragen (Ja/Nein) zu identifizieren.

Ironischerweise lässt sich das Rätsel trotz seines Namens noch erheblich erschweren (man hat nur zwei Fragen für die Lösung, und die Götterworte für Ja und Nein sind vollkommen unbekannt).

Inhalt des Rätsels Die englische Fassung bei Boolos wird hier möglichst wortgetreu übersetzt. Das von Boolos verwendete Begriffspaar DA/JA wurde, nach dem Vorbild von Smullyan, durch DA/BAL ersetzt, um nachfolgend in den deutschen Erläuterungen Missverständnisse zu vermeiden („da“ ist das russische Wort für „ja“; „bal“ das arabische für „ja“ und das balinesische für „nein“).

Originalrätsel in der Fassung von George Boolos

Zusätzliche Hinweise von Boolos: Du kannst einem einzelnen Gott mehr als eine Frage stellen. Die Fragen dürfen von den Antworten auf frühere Fragen abhängen. Ob der Zufallsgott wahr spricht oder nicht sollte man sich so vorstellen, als würde in seinem Kopf eine verborgene Münze geworfen: fällt „Kopf“, spricht er wahr, andernfalls falsch. Der Zufallsgott antwortet auf jede Ja/Nein-Frage mit DA oder BAL.

Erschwerte Fassung Eine verschärfte Version, bei der kein Wort der Göttersprache bekannt ist und nur zwei Fragen erlaubt sind, wurde von Nikolay Novozhilov vorgeschlagen. Sie lässt sich folgendermaßen formulieren:

Hilfsrätsel Boolos führt in seinem Aufsatz von 1996 einfachere Rätsel auf, die nützliche Bausteine für die Gesamtlösung liefern.

Hilfsrätsel zur Originalfassung Löse zunächst nacheinander folgende Rätsel:

Auf einem Tisch liegen (verdeckt) zwei Asse und ein Bube. Du sollst ein As finden. Dazu musst du auf eine der Karten zeigen und dabei eine beliebige Ja/Nein-Frage stellen. Wenn die Karte, auf die du zeigst (und die nicht umgedreht wird) ein As ist, dann erhältst du eine wahrheitsgemäße Antwort; andernfalls eine zufällige. Der Zufallsgott ist abwesend. Durch eine einzige Entscheidungsfrage an einen der verbliebenen Götter sollst du herausfinden, ob Duschanbe in Kirgisien liegt. Die Götter antworten auf Deutsch. Durch eine einzige Entscheidungsfrage an den Gott der Wahrheit sollst du herausfinden, ob Duschanbe in Kirgisien liegt. Er antwortet in Göttersprache.

Hilfsrätsel zur erschwerten Fassung Führe nacheinander aus: Löse zunächst das Originalrätsel, ggf. zuvor die drei Hilfsrätsel dazu. Finde als Nächstes im Kontext des Originalrätsels eine (beliebige) Entscheidungsfrage, auf die der Gott der Wahrheit zwangsläufig anders reagiert als der Gott des Zufalls. Wie zuvor, aber jetzt im Kontext der erschwerten Rätselfassung mit Z als Gott des Zwiespalts. Löse die erschwerte Fassung in zwei Fragen unter der Annahme, dass von der Göttersprache nur das Wort BAL bekannt ist (was entweder ja oder nein bedeutet).

Entstehung und konzeptioneller Hintergrund George Boolos, Mathematiker und Logiker am MIT, publizierte das Rätsel 1996 in der Harvard Review of Philosophy unter dem Titel The Hardest Logic Puzzle EverGeorge Boolos: The Hardest Logic Puzzle Ever. In: Harvard Review of Philosophy. 6, 1996, S. 62–65., https://www.thebigquestions.com/boolos.pdf. Darin schreibt er, eine Übersetzung seines Artikels sei bereits am 16. April 1992 unter dem Titel L’indovinello più difficile del mondo in der italienischen Tageszeitung La Repubblica veröffentlicht worden.

Als Urheber des Rätsels würdigt Boolos seinen Landsmann Raymond Merrill Smullyan: „Some years ago, the logician and puzzle-master Raymond Smullyan devised a logical puzzle that has no challengers I know of for the title of Hardest Logical Puzzle Ever“. Es ist unbekannt, ob und wo Smullyan seinerseits das Rätsel veröffentlicht hatteJedenfalls findet sich derzeit keine Internetquelle. Möglicherweise beschreibt Smullyan dieses Rätsel in einem seiner Bücher. Die Schwierigkeit, nicht zu wissen, welche Worte der Götter für „Ja“ und „Nein“ stehen, geht Boolos zufolge auf den damals in Stanford lehrenden Informatiker und Logiker John McCarthy zurück - wobei unklar bleibt, ob es bereits Smullyan oder erst Boolos war, der diese Anregung aufgegriffen hatte.

1978 hatte Smullyan in seinem BuchRaymond Smullyan: What is the Name of This Book? Englewood Cliffs, New Jersey: Prentice Hall. „What Is the Name of This Book?“ zahlreiche verwandte Rätselvarianten entwickelt. Darin findet man bereits alle Elemente des „schwierigsten Rätsels der Welt“: neben den Grundcharakteren, z. B. wahrheitsliebenden Rittern und verlogenen Knappen, insb. „Zwischencharaktere“, deren Antworten unvorhersehbar sind, und Antworten in einer fremden Sprache mit den Ausdrücken DA/BAL für ja/nein (Zitat) „one of which means yes and the other no“.

Das Gedankenexperiment fiktiver Charaktere, die stets lügen, findet sich bereits in der antiken Philosophie. Ein Rätsel in Kombination mit Charakteren, die im Gegensatz dazu stets die Wahrheit sagen, publizierte im Jahr 1931 Nelson Goodman anonym in der Boston Post. Popkulturell bekannt geworden ist eine Spielart, die sich bereits 1975 in der Doctor Who – Folge Pyramids of Mars findet, die elf Jahre später den Weg auch ins Hollywoodkino und seither noch mehrfach in Fernsehserien fand: dabei treten zwei Personen auf, von denen eine immer lügt und die andere immer die Wahrheit sagt (im Film Labyrinth von 1986 z. B. zwei Wächter), und es gilt, durch eine einzige Frage an eine der beiden eine wichtige Information zu erlangen (im Beispiel, welcher Weg zum Ziel und welcher ins Verderben führt).

Grundmechanismen der Lösung Gott für die zweite Frage bestimmen Alle bekannten Strategien übernehmen Boolos' Ansatz, mit der ersten Frage (an einen beliebigen Gott) einen anderen Gott zu identifizieren, der mit Sicherheit nicht Gott des Zufalls ist und dem man die nächste Frage stellen kann – samt der Erkenntnis, dass es dabei unschädlich ist, wenn man die erste Frage dem Gott des Zufalls stellt (dazu ausführlicher z. B. bei der ersten Frage von Roberts’ Lösung). Dieser Ansatz ist das Ziel von Boolos' erstem Hilfsrätsel.

Logische Verknüpfungen Weiterhin beruhen alle Strategien auf der logischen Verknüpfung von Behauptungen.

XOR / NXOR – Verknüpfung Die XOR / NXOR – Verknüpfung ist für Logikrätsel dieser Art von besonderer Bedeutung, weil sich durch sie Wahrheit und Lüge wechselseitig neutralisierten lassen (worauf Boolos' zweites Hilfsrätsel hinführt), genauso wie auch die unbekannten Bedeutungen der Worte für Ja und Nein (darum geht es bei Boolos' drittem Hilfsrätsel). Einen eleganten und intuitiven Weg, diese Verknüpfung semantisch abzubilden, fand Roberts mit seiner Technik selbstreferenzieller Fragen.

Als XOR-Verknüpfung wird im Folgenden die Frage bezeichnet, ob die kontravalente Verbindung von zwei Behauptungen (im Folgenden "Thesen" genannt) T1 und T2 mithilfe des exklusiven Oder (XOR), bekannt aus der Logik und Informatik, zu einer wahren Aussage führt.

formal: T1 XOR T2 ?

Semantisch entspricht das der Frage, ob von den Thesen T1 und T2 genau eine zutreffend ist (d. h. ob sie unterschiedliche Wahrheitswerte haben).

Die funktional gleichwertig einsetzbare Umkehrung ist die äquivalente Verbindung (NXOR):

formal: T1 NXOR T2 ?

Dies entspricht semantisch der Frage, ob T1 und T2 entweder beide richtig oder beide falsch sind (d. h. ob sie identische Wahrheitswerte haben).

Beispiele für die Anwendung finden sich unten, insb. bei der Darstellung von Boolos' Lösungsansätzen.

Weitere Verknüpfungen Die von Rabern/Rabern vorgestellten Lösungen verwenden zusätzlich die konjunktive AND-Verknüpfung (T1 AND T2? fragt, ob beide Thesen zutreffen) sowie die disjunktive OR-Verknüpfung (T2 OR T2? fragt, ob mindestens eine der Thesen zutrifft).

Fragetechnik und Lösung nach Roberts Im Jahr 2001 stellte T. S. RobertsT. S. Roberts: Some Thoughts About The Hardest Logic Puzzle Ever. In: Journal of Philosophical Logic. 30 (4), S. 609–612, Dezember 2001, researchgate.net eine Lösungstechnik vor, die später auch Rabern/Rabern zum Einsatz brachten. Mit ihr werden die Lösungsfragen nicht nur besser in Alltagssprache formulierbar, sondern auch leichter herleitbar als beim Ansatz von Boolos, wenngleich sich dahinter am Ende die gleichen logischen Grundmuster verbergen.

Roberts’ Grundtrick Roberts’ Ansatz basiert auf kontrafaktischen Fragen, wie sie z. B. die Protagonistin im oben genannten Film „Labyrinth“ einsetzt („Was würde der andere Wächter sagen, wenn ich ihn fragen würde...?“). Er stellt diese aber selbstreferenziell („Was würdest Du sagen, wenn ich Dich fragen würde...?“). Dieser Trick bewirkt, dass sowohl der Gott der Wahrheit als auch der Gott der Lüge dieselbe Antwort geben: die Lüge des lügenden Gottes bezieht sich auf seine eigene (hypothetische) falsche Antwort und hebt sich mit ihr auf. Eine sehr elegante Anwendung der NXOR-Verknüpfung.

Roberts’ erweiterter Trick Zur Überwindung der Sprachbarriere dehnt Roberts die Selbstreferenz auf den Wortlaut der Antwort aus, in folgender Form: „Würdest du BAL sagen, wenn ich dich fragen würde, ob…?“. Antwortet der Gott mit dem Begriff, der in der Frage genannt wurde (im Beispiel BAL), so lässt sich dies als Bestätigung, andernfalls als Verneinung deuten.

Roberts’ erweiterter Trick liefert ein Werkzeug, mit dem sich jede (entscheidbare) Frage so einkleiden lässt, dass man von jedem Gott außer dem Zufallsgott eine verlässliche Antwort erhält und ihre Bedeutung klar ist. Rabern/Rabern bezeichnen diesen Trick als den "Satz der eingebetteten Frage" ('"embedded question lemma"). Zur Veranschaulichung zwei Fragen an einen englischsprachigen Gott – um herauszufinden, ob Rom in Italien liegt:

F1: „Würdest du YES sagen, wenn ich dich fragen würde, ob Rom in Italien liegt?“

Der Gott der Wahrheit erklärt wahrheitsgemäß, dass er YES antworten würde. Der Gott der Lüge würde NO antworten und behauptet also das Gegenteil. Im Ergebnis erwidern beide das in der Frage genannte Wort, nämlich YES.

F2: „Würdest du NO sagen, wenn ich dich fragen würde, ob Rom in Italien liegt?“

Der Gott der Wahrheit erklärt wahrheitsgemäß, dass er NO antworten würde. Der Gott der Lüge würde würde YES antworten und behauptet also das Gegenteil. Im Ergebnis erwidern erneut beide das in der Frage genannte Wort, in diesem Fall NO.

Im Ergebnis verbirgt sich hinter Roberts’ erweitertem Trick die Anwendung von Boolos' Trick - aber in einer sehr intuiviten Formulierung. Bei Boolos hieße die Frage formalisiert

(Rom liegt in Italien) NXOR (DA = JA) NXOR (Du bist W)?

Konkrete Anwendung Eine konkrete Lösungsmöglichkeit nach Roberts sieht so aus:

Frage 1 an A:

Zweck: Einen Gott G ≠ Z finden (der also nicht Gott des Zufalls ist).

Wortlaut: „Wenn ich dich fragen würde, ob B der Gott des Zufalls ist, würdest du dann mit DA antworten?“

Es wird unterstellt, dass A entweder Gott der Wahrheit oder der Lüge ist, und seine Antwort wird daher folgendermaßen interpretiert:

Antwort DA -> B = Z . Also ist C ≠ Z, und man setzt daher G = C Antwort BAL -> B ≠ Z, und man setzt daher G = B.

Sollte die Unterstellung falsch und somit A der Gott des Zufalls sein, ist seine Antwort (im Zweifel) zwar ohne Aussagekraft – aber dann ist sowohl B ≠ Z als auch C ≠ Z, und die vorstehende Zuordnung erreicht ebenfalls ihr Ziel (führt also zu einem Gott G, der sicher nicht Gott des Zufalls ist).

Frage 2 an G:

Zweck: die genaue Identität des in Frage 1 gefundenen Gottes G herausfinden.