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

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

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

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

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

История [ править ]

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

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

Решение [ править ]

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

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

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

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

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

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

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

дает ответ ja, если правдивый ответ на Q - да , и ответ da, если правдивый ответ на 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 или Da , потребуется (еще одно) отрицание исключительной дизъюнкции Ja с результатом шага 3.
   • ¬ ((¬ ((¬ ((¬ (Q ⊕ Бог)) ⊕ Джа)) ⊕ Бог)) ⊕ Джа)

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

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

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

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

• Предположим, джа означает нет, а да - да .

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

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

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

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

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

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

Поведение Рэндома [ править ]

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

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

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

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

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

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

Спросите бога А: «Если бы я спросил:« Вы случайны? » в вашем нынешнем психическом состоянии, вы бы сказали да ? "

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Ричард Уэбб. Три бога, три вопроса: самая сложная логическая головоломка на свете. (New Scientist, том 216, выпуски 2896–2897, 22–29 декабря 2012 г., страницы 50–52.)
• Том Эллис. Даже сложнее, чем самая сложная логическая головоломка.
• Стефан Винтейн. Играя с правдой.
• Вальтер Карниелли. Contrafactuais, contradição eo enigma lógico mais Difícil do mundo. Revista Omnia Lumina. (на португальском)
• Джейми Кондлифф. Самая сложная логическая головоломка (и как ее решить).
• Самая сложная логическая головоломка на свете (страница на сайтах Google)