Самая сложная логическая головоломка

Самая сложная логическая головоломка — логическая головоломка , названная так американским философом и логиком Джорджем Булосом и опубликованная в The Harvard Review of Philosophy в 1996 году. ^{[1] [2]} Статья Булоса включает несколько способов решения задачи. Перевод на итальянский язык был опубликован ранее в газете La Repubblica под названием L'indovinello più difficile del mondo .

Он гласит следующее:

Три бога A, B и C называются в произвольном порядке Истина, Ложь и Случайность. Истина всегда говорит правду, Ложь всегда говорит ложь, но говорит ли Случайность правду или ложь — это совершенно случайный вопрос. Ваша задача — определить личности A, B и C, задав три вопроса «да-нет» ; каждый вопрос должен быть задан ровно одному богу. Боги понимают английский, но ответят на все вопросы на своем родном языке, в котором слова « да» и «нет» — da и ja ^[3] в некотором порядке. Вы не знаете, какое слово что означает .

Булос дает следующие пояснения: ^[1] одному богу можно задать более одного вопроса, вопросы могут зависеть от ответов на более ранние вопросы, а характер ответа Рэндома следует рассматривать как зависящий от подбрасывания честной монеты, скрытого в его мозгу: если монета выпадает орлом, он говорит правду; если решкой, он говорит ложь. ^[4]

Булос приписывает логику Рэймонду Смаллиану создание головоломки, а Джону Маккарти добавление трудности незнания того, что означают da и ja . Связанные с этим головоломки можно найти во всех работах Смаллиана. Например, в « Как называется эта книга?» [ ^5] он описывает остров на Гаити, где половина жителей — зомби (которые всегда лгут), а половина — люди (которые всегда говорят правду). Он объясняет, что «ситуация чрезвычайно осложняется тем фактом, что, хотя все местные жители прекрасно понимают английский язык, древнее табу острова запрещает им когда-либо использовать неместные слова в своей речи. Поэтому всякий раз, когда вы задаете им вопрос «да-нет», они отвечают Bal или Da — одно из которых означает «да» , а другое — « нет » . Проблема в том, что мы не знаем, какое из Bal или Da означает «да» , а какое — «нет». В «Загадке Шехерезады » есть и другие связанные с этим головоломки . ^{[6] [7]}

Головоломка основана на головоломках «Рыцари и лжецы» . Одним из мест действия этой головоломки является вымышленный остров, населенный только рыцарями и лжецами, где рыцари всегда говорят правду, а лжецы всегда лгут. Посетитель острова должен задать ряд вопросов с ответами «да» или «нет», чтобы узнать, что ему нужно знать (конкретика которых различается в разных версиях головоломки). Одна из версий этих головоломок была популяризирована сценой в фэнтезийном фильме 1986 года «Лабиринт» . Есть две двери, у каждой из которых есть один охранник. Один охранник всегда лжет, а другой всегда отвечает правдиво. Одна дверь ведет в замок, а другая ведет к «верной смерти». Головоломка заключается в том, чтобы выяснить, какая дверь ведет в замок, задав одному из охранников один вопрос. В фильме главный герой делает это, спрашивая: «Скажет ли он [другой охранник] мне, что эта дверь ведет в замок?»

Булос предоставил свое решение в той же статье, в которой он представил головоломку. Булос утверждает, что «первый шаг — найти бога, который, как вы можете быть уверены, не является Случайным, и, следовательно, является либо Истинным, либо Ложным». ^[1] Существует много разных вопросов, которые позволят достичь этого результата. Одна из стратегий — использовать в своих вопросах сложные логические связки (либо двуусловные , либо эквивалентную конструкцию).

Вопрос Булоса был таким: «А»:

Означает ли da «да» тогда и только тогда, когда вы — Истина, тогда и только тогда, когда B — Случайно? ^[1]

Эквивалентно:

Верны ли нечетные числа из следующих утверждений: da означает «да» , you — True, B — Random?

Робертс (2001) и независимо Раберн и Раберн (2008) заметили, что решение головоломки можно упростить, используя определенные контрфактуальные утверждения . ^{[6] [8]} Ключ к этому решению заключается в том, что для любого вопроса Q, предполагающего ответ «да/нет», задавая вопрос «Истина» или «Ложь»:

Если бы я спросил вас «Q», вы бы ответили «ja» ?

приводит к ответу ja, если правдивый ответ на Q — да , и ответу da, если правдивый ответ на Q — нет (Rabern и Rabern (2008) называют этот результат леммой о встроенном вопросе). Причину, по которой это работает, можно увидеть, изучив логическую форму ожидаемого ответа на вопрос. Эта логическая форма ( булево выражение ) представлена ​​ниже (« Q» истинно, если ответ на Q — «да», « Бог» истинно, если бог, которому задан вопрос, выступает в роли говорящего правду, и «Ja» истинно, если значение Ja — «да»):

1. То, как бог выберет ответ на вопрос Q, определяется отрицанием исключающей дизъюнкции между Q и Богом (если ответ на вопрос Q и природа бога противоположны, то ответ, данный богом, обязательно будет «нет», а если они одинаковы, то ответ обязательно будет «да»):
   • ¬ ( Q ⊕ Бог)
2. Будет ли ответ, данный богом, Ja или нет, снова определяется отрицанием исключающей дизъюнкции между предыдущим результатом и Ja.
   • ¬ ( ( ¬ ( Q ⊕ Бог)) ⊕ Джа )
3. Результат шага два дает правдивый ответ на вопрос: «Если я спрошу тебя Q, ты скажешь ja?» Какой ответ даст Бог, можно определить, используя рассуждения, аналогичные тем, что использовались в шаге 1.
   • ¬ ( ( ¬ ( ( ¬ ( Q ⊕ Бог)) ⊕ Джа )) ⊕ Бог )
4. Наконец, чтобы узнать, будет ли этот ответ Ja или Da , потребуется (еще одно) отрицание исключающей дизъюнкции Ja с результатом шага 3.
   • ¬ ( ( ¬ ( ( ¬ ( ( ¬ ( Q ⊕ Бог) ) ⊕ Джа ) ) ⊕ Бог ) ) ⊕ Джа )

Это окончательное выражение оценивается как истинное, если ответ Ja , и ложное в противном случае. Восемь случаев рассмотрены ниже (1 представляет истинное, а 0 ложное):

Сравнение первой и последней колонок ясно показывает, что ответ Ja только тогда, когда ответ на вопрос — «да». Те же результаты применимы, если бы вместо этого был задан вопрос: «Если бы я спросил вас Q, вы бы ответили Da?», потому что оценка контрфактуальности не зависит поверхностно от значений Ja и Da. Каждый из восьми случаев эквивалентно обоснован ниже словами:

• Предположим, что ja означает «да» , а da означает «нет» .

1. True спрашивают и он отвечает ja . Поскольку он говорит правду, правдивый ответ на Q — ja , что означает да .
2. True спрашивают, и он отвечает da . Поскольку он говорит правду, правдивый ответ на Q — da , что означает no .
3. False спрашивают и отвечают ja . Поскольку он лжет, то если бы вы спросили его Q, он бы ответил da . Он бы лгал, поэтому правдивый ответ на Q — ja , что означает да .
4. False спрашивают и отвечают da . Поскольку он лжет, то, если бы вы спросили его Q, он бы ответил ja . Он бы солгал, поэтому правдивый ответ на Q — da , что означает no .

• Предположим, что ja означает «нет» , а da означает «да» .

1. True спрашивают и отвечают ja . Поскольку он говорит правду, правдивый ответ на Q — da , что означает да .
2. True спрашивают, и он отвечает da . Поскольку он говорит правду, правдивый ответ на Q — ja , что означает no .
3. False спрашивают и он отвечает ja . Поскольку он лжет, то, если бы вы спросили его Q, он бы ответил ja . Он бы солгал, поэтому правдивый ответ на Q — da , что означает да .
4. False спрашивают и отвечают da . Поскольку он лжет, то, если бы вы спросили его Q, он бы ответил da . Он бы лгал, поэтому правдивый ответ на Q — ja , что означает нет.

Независимо от того, лжет ли заданный вопрос богу или нет, и независимо от того, какое слово означает «да» , а какое « нет» , вы можете определить, является ли правдивым ответ на вопрос « да» или «нет» .

Приведенное ниже решение строит свои три вопроса с использованием леммы, описанной выше. ^[6]

Q1: Спросите бога B: «Если бы я спросил тебя «Случайно ли A?», ты бы ответил ja ?». Если B отвечает ja , то либо B является Случайным (и отвечает случайным образом), либо B не является Случайным, и ответ указывает на то, что A действительно Случайно. В любом случае, C не является Случайным. Если B отвечает da , то либо B является Случайным (и отвечает случайным образом), либо B не является Случайным, и ответ указывает на то, что A не Случайно. В любом случае, вы знаете личность бога, который не является Случайным.

Q2: Идите к богу, который был определен как неслучайный в предыдущем вопросе (A или C), и спросите его: «Если бы я спросил тебя: «Ты Ложь?», ты бы ответил ja ?». Поскольку он не Случайный, ответ da указывает на то, что он Истина, а ответ ja указывает на то, что он Ложь.

Q3: Задайте тому же богу вопрос: «Если бы я спросил тебя «Случайно ли B?», ты бы ответил ja ?». Если ответ ja , то B — Случайно; если ответ da , то бог, с которым ты еще не говорил, — Случайно. Оставшегося бога можно определить методом исключения.

Третье поясняющее замечание Булоса объясняет поведение Рэндома следующим образом: ^[6]

Правдивы ли слова Рэндома или нет, следует считать результатом подбрасывания монеты, спрятанного в его мозгу: если выпадает орел, он говорит правду, если решка — ложь.

Это не говорит о том, подбрасывается ли монета для каждого вопроса или для каждой «сессии», то есть для всей серии вопросов. Если интерпретировать это как один случайный выбор, который длится в течение сессии, Раберн и Раберн показывают, что полезные ответы могут быть извлечены даже из Случайного; ^[6] это потому, что контрфактуальность была разработана таким образом, что независимо от того, был ли отвечающий (в данном случае Случайный) говорящим правду или лжецом, правдивый ответ на вопрос Q был бы ясен.

Другая возможная интерпретация поведения Рэндома, когда он сталкивается с контрфактуальным, заключается в том, что он отвечает на вопрос в его совокупности после подбрасывания монеты в голове, но вычисляет ответ на Q в своем предыдущем состоянии ума, пока задается вопрос. И снова, это делает бесполезным спрашивание Рэндома о контрфактуальном. Если это так, небольшое изменение вопроса выше дает вопрос, который всегда вызовет осмысленный ответ от Рэндома. Изменение заключается в следующем:

Если бы я спросил вас о вашем текущем психическом состоянии , вы бы ответили «ja» ? ^[6]

Это эффективно извлекает из Рэндома личности правдолюбца и лжеца и заставляет его быть только одной из них. При этом головоломка становится совершенно тривиальной, то есть правдивые ответы могут быть легко получены. Однако это предполагает, что Рэндом решил солгать или сказать правду до определения правильного ответа на вопрос — чего-то, что не указано в головоломке или в пояснительном замечании.

Спросите бога А: «Если бы я спросил тебя: «Ты случайный?» в твоем текущем психическом состоянии, ты бы ответил ja ?»

1. Если A отвечает ja , A — случайный выбор: Спросите бога B: «Если бы я спросил тебя: «Ты верен?», ты бы ответил ja ?»
   • Если B отвечает ja , то B — Истина, а C — Ложь.
   • Если B отвечает da , B — Ложь, а C — Истина. В обоих случаях головоломка решена.
2. Если А отвечает da , то А не является случайным: Спросите бога А: «Если бы я спросил тебя: «Ты верен?», ты бы ответил ja ?»
   • Если ответ A — ja , то A — True.
   • Если ответ А — да , то А — Ложь.
3. Спросите бога А: «Если бы я спросил тебя: «Случайно ли число B?», ты бы ответил ja ?»
   • Если ответ A — ja , то B — случайный, а C — противоположность A.
   • Если ответ A — da , то C — случайный, а B — противоположность A.

Можно элегантно получить правдивые ответы в ходе решения исходной задачи, как пояснил Булос («если монета падает орлом, он говорит правду; если решкой, он говорит ложь»), не полагаясь на какие-либо якобы невысказанные предположения, внеся дополнительные изменения в вопрос:

Если бы я задал вам вопрос «В», и если бы вы ответили так же правдиво, как вы отвечаете на этот вопрос , вы бы ответили «ja» ?

Здесь единственное предположение заключается в том, что Рэндом, отвечая на вопрос , либо отвечает правдиво («говорит правдиво»), ЛИБО отвечает ложно («говорит ложно»), что явно является частью разъяснений Булоса. Исходная немодифицированная задача (с разъяснениями Булоса) таким образом может рассматриваться как «Самая сложная логическая головоломка из когда-либо существовавших» с самым элегантным и простым на вид решением.

Раберн и Раберн (2008) предлагают внести поправку в оригинальную головоломку Булоса, чтобы случайность была действительно случайной. Изменение заключается в замене третьего поясняющего замечания Булоса на следующее: ^[6]

Следует считать, что ответ Рэндома на вопрос «ja» или «da» зависит от подбрасывания монеты, которое происходит в его мозгу: если выпадает орел, он говорит «ja» ; если решка, он говорит «da» .

С этой модификацией решение головоломки требует более тщательного допроса бога, приведенного в верхней части раздела «Решение» .

В работе «Простое решение самой сложной логической головоломки » ^[6] Брайан Раберн и Лэндон Раберн предлагают вариант головоломки: бог, столкнувшись с парадоксом, не скажет ни «ja» , ни «da» и вместо этого вообще не ответит. Например, если на вопрос «Вы собираетесь ответить на этот вопрос словом, которое на вашем языке означает « нет» ?» ответить «Истиной», он не сможет ответить правдиво. (В статье это представлено как взрыв его головы : «...они непогрешимые боги! У них есть только один выход — их головы взрываются».) Разрешение случая «взрывающейся головы» дает еще одно решение головоломки и вводит возможность решения головоломки (модифицированной и оригинальной) всего за два вопроса, а не за три. В поддержку решения головоломки с двумя вопросами авторы решают похожую более простую головоломку, используя всего два вопроса.

Три бога A, B и C называются в некотором порядке Зефиром , Эвром и Эолом . Боги всегда говорят правду. Ваша задача — определить личности A, B и C, задавая вопросы с ответами «да-нет»; каждый вопрос должен быть задан только одному богу. Боги понимают английский язык и ответят на английском языке.

Обратите внимание, что эта головоломка решается тривиально тремя вопросами. Более того, для решения головоломки в два вопроса доказывается следующая лемма .

Лемма о закалённом лжеце. Если мы спросим A «Правда ли, что {[(вы собираетесь ответить «нет» на этот вопрос) И (B — это Зефир)] ИЛИ (B — это Эврус)}?», ответ «да» означает, что B — это Эврус, ответ «нет» означает, что B — это Эол, а взрывающаяся голова означает, что B — это Зефир. Следовательно, мы можем определить личность B за один вопрос.

Используя эту лемму, легко решить головоломку за два вопроса. Раберн и Раберн (2008) используют похожий трюк (умеряя парадокс лжеца), чтобы решить исходную головоломку всего за два вопроса. Усквиано (2010) использует эти методы, чтобы предоставить решение с двумя вопросами для измененной головоломки. ^{[9] [10]} Решения с двумя вопросами как для исходной, так и для измененной головоломки используют тот факт, что некоторые боги не могут ответить на определенные вопросы. Ни True, ни False не могут дать ответ на следующий вопрос.

Ответили бы вы так же, как Рэндом, на вопрос «Находится ли Душанбе в Киргизии ?»

Поскольку измененный Random отвечает действительно случайным образом, ни True, ни False не могут предсказать, ответит ли Random ja или da на вопрос о том, находится ли Душанбе в Киргизии. Учитывая это незнание, они не смогут сказать правду или солгать — поэтому они будут молчать. Однако Random, который извергает случайную чушь, не будет иметь проблем с изверганием либо ja , либо da . Uzquiano (2010) использует эту асимметрию, чтобы предоставить решение из двух вопросов для измененной головоломки. Тем не менее, можно предположить, что боги обладают «пророческой способностью предсказывать ответы Random еще до подбрасывания монеты в мозгу Random?» ^[9] В этом случае решение из двух вопросов все еще доступно с использованием самореферентных вопросов в стиле, использованном в Rabern и Rabern (2008).

Ответили бы вы «ja» на вопрос «ответили бы вы «da» на этот вопрос?»

Здесь снова ни True, ни False не могут ответить на этот вопрос, учитывая их обязательства говорить правду и лгать соответственно. Они вынуждены отвечать ja на всякий случай, если ответ, который они обязаны дать, будет da , а этого они сделать не могут. Как и прежде, они пострадают от взрыва мозга. Напротив, Random будет бездумно извергать свою чушь и наугад отвечать ja или da . ​​Uzquiano (2010) также использует эту асимметрию, чтобы предоставить решение модифицированной головоломки из двух вопросов. ^{[9] [10]} Однако собственная модификация головоломки Uzquiano, которая устраняет эту асимметрию, позволяя Random либо отвечать «ja», «da», либо молчать, не может быть решена менее чем за три вопроса. ^[11]

• Ричард Уэбб, Три бога, три вопроса: самая сложная логическая головоломка. (New Scientist, том 216, выпуски 2896–2897, 22–29 декабря 2012 г., страницы 50–52.)
• Сможете ли вы решить самую сложную логическую головоломку?
• Джейсон Розенхаус, Рыцари, Лжецы, Нормальные и Нейтральные
• Том Эллис, Даже сложнее самой сложной логической головоломки.
• Эндрю Бьюкенен и Джон Конвей , Островная история для молодых антропологов
• Джейми Кондлифф, Самая сложная логическая головоломка (и как ее решить).
• Франческо Чирауло и Самуэле Маскио, Решение задачи «рыцари и лжецы» с помощью одного уравнения
• Дэниел Валлстром, Как решить «Самую сложную логическую головоломку» и ее обобщение
• Раберн и Раберн, «В ​​защиту решения самой сложной логической головоломки из когда-либо существовавших с помощью двух вопросов»