«Самая сложная логическая головоломка»[1] (итал. L'indovinello più difficile del mondo) — название логической задачи, предложенной американским философом и логиком Джорджем Булосом в итальянской газете «la Repubblica» в 1992 году:
Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая либо говорит правду, либо лжёт, что определяется случайным образом. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Каждый вопрос задаётся только одному богу, но можно задавать одному богу более одного вопроса. Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja», причём неизвестно, какое слово обозначает «да», а какое «нет».
Булос указывает логика Рэймонда Смаллиана как автора задачи и Джона Маккарти за увеличение сложности задачи из-за неясных трактовок «da» и «ja». Похожие задачи есть в книгах Смаллиана[2], например, он описывает остров, где половина жителей зомби (они постоянно лгут), а другая половина — люди (они постоянно говорят правду). Ситуацию усложняет факт, что жители острова прекрасно нас понимают, но древнее табу запрещает им использовать неродные слова. Поэтому они используют ответы «bal» или «da», которые означают «да» и «нет», причём неясно, какое из них что обозначает. Есть ещё ряд подобных головоломок в книге «The Riddle of Scheherazade». Всё это разновидности широко известных задач о рыцарях и лжецах Смаллиана.
Одна из таких задач была освещена в фильме «Лабиринт»: есть 2 двери и 2 стражника, один всегда говорит правду, второй всегда лжёт. Одна дверь ведёт к замку, вторая — к гибели. Смысл головоломки состоит в том, чтобы узнать, какая дверь ведёт к замку, задав один вопрос одному стражнику. В фильме Сара спрашивала: «Скажет ли он [другой стражник] мне, что эта дверь ведёт к замку?»[3]
Булос предложил решение задачи в той же статье, где он и опубликовал саму задачу. Он заявил, что первым вопросом мы должны найти бога, который не является богом случая, то есть является либо богом правды, либо богом лжи. Есть множество вопросов, которые могут быть заданы для достижения этой цели. Одна из стратегий — использование сложных логических связей в самом вопросе.
Вопрос Булоса: «Означает ли „da“ „да“, если и только если ты бог правды, а бог B — бог случая?». Другой вариант вопроса: «Является ли нечётным число истинных утверждений в следующем списке: ты — бог лжи, „ja“ означает „да“, B — бог случая?»