Самая сложная логическая головоломка на свете - The Hardest Logic Puzzle Ever

Самая сложная логическая головоломка на свете это логическая головоломка так называют американцы философ и логик Джордж Булос и опубликовано в Гарвардский обзор философии в 1996 г.[1] Статья Boolos включает несколько способов решения проблемы. Перевод на Итальянский был опубликован ранее в газете La Repubblica, под заголовком L'indovinello più difficile del mondo.

Утверждается следующее:

Три бога A, B и C называются без определенного порядка Истинным, Ложным и Случайным. Истинный всегда говорит правду, Ложь всегда говорит ложно, но говорит ли Рэндом правдиво или ложно - вопрос совершенно случайный. Ваша задача - определить личности A, B и C, задав три вопроса. Да, без вопросов; каждый вопрос должен быть задан ровно одному богу. Боги понимают английский, но ответят на все вопросы на своем родном языке, в котором слова для да и нет находятся да и я, в некотором порядке. Вы не знаете, какое слово какое означает.

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

История

Булос доверяет логику Раймонд Смуллян как создатель головоломки и Джон Маккарти с добавлением трудности незнания да и я иметь в виду. Соответствующие загадки можно найти в трудах Смулляна. Например, в Как называется эта книга?,[4] он описывает гаитянский остров, где половина жителей - зомби (которые всегда лгут), а половина - люди (которые всегда говорят правду). Он объясняет, что «ситуация чрезвычайно усложняется тем фактом, что, хотя все туземцы прекрасно понимают английский, древнее табу острова запрещает им когда-либо использовать в своей речи неродные слова. Поэтому всякий раз, когда вы задаете им вопрос типа« да-нет » они отвечают Бал или же Да- одно из которых означает да и другие нет. Проблема в том, что мы не знаем, какой из Бал или же Да средства да и что означает нет." Есть и другие связанные головоломки в Загадка Шахерезады.[5][6]

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

Решение

Булос представил свое решение в той же статье, в которой он представил загадку. Булос заявляет, что «первый шаг - найти бога, который, как вы можете быть уверены, не является случайным и, следовательно, является либо истинным, либо ложным».[2] Есть много разных вопросов, которые позволят достичь такого результата. Одна из стратегий - использовать сложные логические связки в ваших вопросах (либо двухусловные или некоторая эквивалентная конструкция).

Вопрос Булоса заключался в том, чтобы задать А:

Делает да иметь в виду да если и только если вы истинны, если и только если B является случайным?[2]

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

Верны нечетное количество следующих утверждений: вы Ложь, да средства да, B случайно?

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

Если бы я спросил вас Q, вы бы сказали я?

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

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

Это последнее выражение истинно, если ответ Ja, и false в противном случае. Ниже описаны восемь случаев (1 соответствует истине, а 0 - ложь):

Q

Верно, если ответ на

Q - "да"

Бог

Верно, если бог ведет себя

как правдивый

Ja

Верно, если значение

Ja Да'

Шаг 1

(Ответ Бога на вопрос)

Шаг 2

(Это Ja?)

Шаг 3

(Божий ответ на противное)

Шаг 4

(Это Ja?)

0001010
0011100
0100110
0110000
1000101
1010011
1101001
1111111

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

  • Предположить, что я средства да и да средства нет.
  1. Правда спрашивается и отвечает я. Поскольку он говорит правду, правдивый ответ на вопрос Q - я, что значит да.
  2. Правда спрашивается и отвечает да. Поскольку он говорит правду, правдивый ответ на вопрос Q - да, что значит нет.
  3. Ложь задается и отвечает я. Поскольку он лжет, значит, если бы вы спросили его Q, он бы вместо этого ответил да. Он бы солгал, поэтому правдивый ответ на вопрос Q - я, что значит да.
  4. Ложь задается и отвечает да. Поскольку он лжет, значит, если бы вы спросили его Q, он бы ответил: я. Он бы солгал, поэтому правдивый ответ на вопрос Q - да, что значит нет.
  • Предполагать я средства нет и да средства да.
  1. Правда спрашивается и отвечает я. Поскольку он говорит правду, правдивый ответ на вопрос Q - да, что значит да.
  2. Правда спрашивается и отвечает да. Поскольку он говорит правду, правдивый ответ на вопрос Q - я, что значит нет.
  3. Ложь задается и отвечает я. Поскольку он лжет, значит, если бы вы спросили его Q, он бы ответил: я. Он бы солгал, поэтому правдивый ответ на вопрос Q - да, что значит да.
  4. Ложь задается и отвечает да. Поскольку он лжет, значит, если бы вы спросили его Q, он бы вместо этого ответил да. Он бы солгал, поэтому правдивый ответ на вопрос Q - я, что значит нет.

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

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

В1: Спросите бога Б: «Если бы я спросил вас:« Случайно ли? », Вы бы сказали я? ". Если B отвечает я, либо B является случайным (и отвечает случайным образом), либо B не является случайным, и ответ указывает, что A действительно является случайным. В любом случае C не является случайным. Если B отвечает да, либо B является случайным (и отвечает случайным образом), либо B не является случайным, и ответ указывает, что A не является случайным. В любом случае, вы знаете личность бога, который не является случайным.
Q2: Идите к богу, который был идентифицирован как нет будучи случайным по предыдущему вопросу (либо A, либо C), и спросите его: «Если бы я спросил вас:« Вы ложны? », вы бы сказали я? ". Поскольку он не случайный, ответ да указывает на то, что он Верен, и ответ я указывает, что он Ложь.
Q3: Задайте тому же богу вопрос: «Если бы я спросил вас:« Является ли B случайным? », Вы бы сказали я? ". Если ответ я, B - случайный; если ответ да, бог, с которым вы еще не говорили, является случайным. Оставшегося бога можно определить путем исключения.
Дело12345678910111213141516
АИстинныйИстинныйЛожьСлучайныйЛожьСлучайныйИстинныйИстинныйЛожьСлучайныйЛожьСлучайный
BЛожьСлучайныйИстинныйИстинныйСлучайныйЛожьЛожьСлучайныйИстинныйИстинныйСлучайныйЛожь
CСлучайныйЛожьСлучайныйЛожьИстинныйИстинныйСлучайныйЛожьСлучайныйЛожьИстинныйИстинный
ДададададададаНетНетНетНетНетНет
JaНетНетНетНетНетНетдададададада
Действительно ли А случайно?НетНетНетдаНетдаНетНетНетдаНетда
Как бы Б ответил "Случайно?"английскийдаЛибоНетдаЛибоНетдаЛибоНетдаЛибоНет
Их языкДаЛибоJaДаЛибоJaJaЛибоДаJaЛибоДа
Ответ B на вопрос 1: «Если бы я спросил вас:« Случайно? », Вы бы сказали я?"английскийдаЛибодаНетЛибоНетНетЛибоНетдаЛибода
Их языкДаЛибоДаJaЛибоJaДаЛибоДаJaЛибоJa
ДаJaДаJaДаJaДаJa
Таким образом, __ (далее именуемый X) не является случайным.ААCАCАCCААCАCАCC
Действительно ли X ложно?НетНетдадададаНетНетНетНетдадададаНетНет
Как бы X ответил: "Вы ложь?"английскийНетНетНетНетНетНетНетНетНетНетНетНетНетНетНетНет
Их языкJaJaJaJaJaJaJaJaДаДаДаДаДаДаДаДа
Ответ X на вопрос 2: «Если бы я спросил вас:« Вы ложны? », Вы бы сказали я?"английскийдадаНетНетНетНетдадаНетНетдадададаНетНет
Их языкДаДаJaJaJaJaДаДаДаДаJaJaJaJaДаДа
Таким образом, X - это __. ИстинныйИстинныйЛожьЛожьЛожьЛожьИстинныйИстинныйИстинныйИстинныйЛожьЛожьЛожьЛожьИстинныйИстинный
Действительно ли B случайно?НетдаНетНетдаНетНетдаНетНетдаНет
Как X ответил бы "Случайно ли B?"английскийНетдаНетдадаНетдаНетНетдаНетдадаНетдаНет
Их языкJaДаJaДаДаJaДаJaДаJaДаJaJaДаJaДа
Ответ X на вопрос 3: «Если бы я спросил вас:« Случайно ли B? », Вы бы сказали я?"английскийдаНетНетдадаНетНетдаНетдадаНетНетдадаНет
Их языкДаJaJaДаДаJaJaДаДаJaJaДаДаJaJaДа
Таким образом, __ является случайным.CBBCАBBАCBBCАBBА
Таким образом, путем исключения (Буква) становится (Имя).ПисьмоBCАBBCАBBCАBBCАB
ИмяЛожьЛожьИстинныйИстинныйИстинныйИстинныйЛожьЛожьЛожьЛожьИстинныйИстинныйИстинныйИстинныйЛожьЛожь

Поведение Рэндома

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

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

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

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

Если бы я спросил вас Q в вашем текущем психическом состояниивы бы сказали я?[5]

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

Спросите бога А: «Если бы я спросил:« Вы случайны? » в вашем нынешнем психическом состоянии, вы бы сказали я?"
  1. Если А отвечает я, A является случайным: спросите бога B: «Если бы я спросил вас:« Верно ли вы? », Вы бы сказали я?"
    • Если B отвечает я, B истинно, а C ложно.
    • Если B отвечает да, B - ложь, а C - истина. В обоих случаях загадка решена.
  2. Если А отвечает да, A не является случайным: спросите бога A: «Если бы я спросил вас:« Ты прав? », Вы бы сказали я?"
    • Если А отвечает я, A верно.
    • Если А отвечает да, A - ложь.
  3. Спросите бога А: «Если бы я спросил:« Случайно ли Б? », Вы бы сказали я?"
    • Если А отвечает я, B является случайным, а C является противоположностью A.
    • Если А отвечает да, C является случайным, а B является противоположностью A.


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

Если бы я спросил вас Q, и если бы вы ответили так же правдиво, как и на этот вопросвы бы сказали я?

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


Rabern и Rabern (2008) предлагают внести поправку в исходную головоломку Boolos так, чтобы Random был на самом деле случайным. Модификация заключается в замене третьего поясняющего замечания Булоса следующим:[5]

Говорит ли Рэндом я или же да следует рассматривать как зависящую от подбрасывания монеты, спрятанной в его мозгу: если монета падает орлом, он говорит я; если решка, он говорит да.

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

Вопросы без ответа и взрывающиеся боги

В Простое решение самой сложной логической головоломки,[5] Б. Раберн и Л. Раберн предлагают вариант загадки: бог, столкнувшись с парадоксом, не скажет ни то, ни другое. я ни да а вместо этого вообще не отвечаю. Например, если на вопрос «Собираетесь ли вы ответить на этот вопрос словом, которое означает нет на вашем языке? "ставится на" Верно ", он не может ответить правдиво. (В документе это указано как его голова взрывается, "... они непогрешимые боги! У них есть только один выход - их головы взрываются.") Допущение случая "взрывающейся головы" дает еще одно решение головоломки и вводит возможность решения головоломки (измененной и оригинальной) в всего два вопроса, а не три. В поддержку решения головоломки с двумя вопросами авторы решают аналогичную более простую головоломку, используя всего два вопроса.

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

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

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

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

Вы бы ответили так же, как Рэндом, на вопрос: Душанбе в Киргизия ?'?

Поскольку измененный Random отвечает действительно случайным образом, ни True, ни False не могут предсказать, ответит ли Random я или же да на вопрос, находится ли Душанбе в Киргизии. Учитывая это невежество, они не смогут сказать правду или солгать - поэтому они будут хранить молчание. А вот случайный, кто изливает случайную чушь, не будет иметь проблем и с изливом. я или же да. Узкиано (2010) использует эту асимметрию, чтобы дать ответ на два вопроса модифицированной головоломки. Тем не менее, можно предположить, что боги обладают «оракульной способностью предсказывать ответы Рэндома еще до того, как в его мозгу подбрасывается монета?»[8] В этом случае решение из двух вопросов по-прежнему доступно с использованием вопросов с самореференцией в стиле, используемом в Rabern and Rabern (2008).

Вы бы ответили я на вопрос, ответите ли вы да на этот вопрос?

Здесь снова ни True, ни False не могут ответить на этот вопрос, учитывая их обязательства говорить правду и ложь соответственно. Они вынуждены отвечать я на всякий случай ответ, который они хотят дать, будет да и они не могут этого сделать. Как и раньше, их ждет взрыв головы. Напротив, Рэндом будет бездумно изливать свою чушь и беспорядочно отвечать. я или же да. Узкиано (2010) также использует эту асимметрию, чтобы дать ответ на два вопроса модифицированной головоломки.[8][9] Однако собственная модификация головоломки Ускиано, которая устраняет эту асимметрию, позволяя Рэндому либо отвечать «джа», «да», либо хранить молчание, не может быть решена менее чем за три вопроса.[10]


Рекомендации

  1. ^ Джордж Булос, «Самая сложная логическая головоломка на свете». Гарвардский обзор философии, Том 6 (1996), стр.62-65 https://doi.org/10.5840/harvardreview1996615.
  2. ^ а б c Булос, Джордж (1996). "Самая сложная логическая головоломка" (PDF). Гарвардский обзор философии. 6: 62–65. Дои:10.5840 / harvardreview1996615.
  3. ^ Обратите внимание, что случайный бог в головоломке Булоса Бог, который действует случайным образом либо как правдивый, либо как лжец. Это отличается от бог, который случайным образом отвечает "да" или "нет". Один из обычных приемов решения многих логических задач - составить (возможно, составной) вопрос, который заставляет обе правду и лжец, чтобы ответить «да». На такой вопрос человек, который случайным образом выбирает роль правды или лжеца, все равно вынужден отвечать «да», но человек, который отвечает случайным образом, может ответить «да» или «нет».
  4. ^ Смуллян, Раймонд (1978). Как называется эта книга?. Энглвуд Клиффс, Нью-Джерси: Prentice Hall. С. 149–156.
  5. ^ а б c d е ж грамм час Rabern, B .; Раберн, Л. (2008). «Простое решение самой сложной логической головоломки» (PDF). Анализ. 68 (298): 105. Дои:10.1111 / j.1467-8284.2007.00723.x.
  6. ^ Смуллян, Раймонд (1997). Загадка Шахерезады. Нью-Йорк: A. A. Knopf, Inc.
  7. ^ Робертс, Т. С. (2001). "Некоторые мысли о самой сложной логической головоломке". Журнал философской логики. 30 (6): 609–612. Дои:10.1023 / а: 1013344220298. S2CID  207556092.
  8. ^ а б c Ускиано, Г. (2009). «Как решить самую сложную логическую головоломку в двух вопросах». Анализ. 70: 39–44. Дои:10.1093 / анализ / anp140.
  9. ^ а б Раберн, Брайан и Раберн, Лэндон. «В защиту двух вопросов - решение самой сложной логической головоломки». dropbox.com
  10. ^ Wheeler, G .; Бараона, П. (2011). «Почему самую сложную логическую головоломку нельзя решить менее чем за три вопроса» (PDF). Журнал философской логики. 41 (2): 493. Дои:10.1007 / s10992-011-9181-7. S2CID  33036814.

внешняя ссылка